Chu trình Hamilton trong đồ thị tách cực G  S(I K,E) với deg(u)  2 với mọi uI

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 cảm sinh trên là đồ thị rỗng và đồ thị con của cảm sinh trên 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 các vấn đề tổ hợp và khoa học máy tính như bài toán đóng gói và xếp ba lô trong quy hoạch nguyên, lý thuyết matroid, nghiên cứu hàm Boolean,….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à với mọi. Chúng ta chứng minh được rằng đồ thị tách cực có chu trình Hamilton khi và chỉ khi với mọi và với mọi.