Về chu trình Hamilton trong đồ thị tách cực

Tóm tắt

Đồ thị được gọi là đồ thị tách cực nếu tồn tại phân hoạch sao cho đồ thị con của G cảm sinh trên I là đồ thị rỗng và đồ thị con của G cảm sinh trên K là đồ thị đầy đủ. Chúng ta ký hiệu đồ thị tách cực đó là. Khái niệm đồ thị tách cực được định nghĩa vào năm 1977 bởi S. Foldes và P.L. Hammer. Các đồ thị này đã và đang được nghiên cứu nhiều bởi vì chúng có liên quan nhiều đến các vấn đề về tổ hợp. Mặt khác, một trong những vấn đề cơ bản của lý thuyết đồ thị là bài toán Hamilton. Trong bài báo này chúng ta sẽ nghiên cứu sự tồn tại chu trình Hamilton trong lớp đồ thị tách cực với và chứng minh được rằng đồ thị tách cực G có chu trình Hamilton khi và chỉ khi khi với mọi, đồ thị có đường Hamilton.