Khái niệm đồ thị tách cực được định nghĩa vào năm 1977 bởi S. Foldes và . 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. | 112 Lê Xuân Hùng VỀ CHU TRÌNH HAMILTON TRONG ĐỒ THỊ TÁCH CỰC ON HAMILTON CYCLES IN SPLIT GRAPHS Lê Xuân Hùng Trường Đại học Tài nguyên và Môi trường Hà Nội Email lxhung@ Tóm tắt - Đồ thị G V E được gọi là đồ thị tách cực nếu tồn Abstract - A graph G V E is called a split graph if there tại phân hoạch V I K sao cho đồ thị con của G cảm sinh exists a partition V I K such that the subgraphs of G trên I là đồ thị rỗng và đồ thị con của G cảm sinh trên K là đồ thị induced by I and K are empty and complete recpectively. We will đầy đủ. Chúng ta ký hiệu đồ thị tách cực đó là S I K E . Khái denote such a graph by S I K E . The notion of split graphs niệm đồ thị tách cực được định nghĩa vào năm 1977 bởi S. Foldes was introduced in 1977 by S. Foldes and . Attention và . Hammer. Các đồ thị này đã và đang được nghiên cứu nhiều has been paid to these graphs because of their connection with bởi vì chúng có liên quan nhiều đến các vấn đề về tổ hợp. Mặt many combinatorial problems. Moreover one of the fundamental khác một trong những vấn đề cơ bản của lý thuyết đồ thị là bài problems in graph theory is the hamiltonian problem. In this paper toán Hamilton. Trong bài báo này chúng ta sẽ nghiên cứu sự tồn we characterize Hamiltonian graphs in the class of split graphs with tại chu trình Hamilton trong lớp đồ thị tách cực với 3 3 G I 1 . We show that G has Hamilton cycle if and G I 1 và chứng minh được rằng đồ thị tách cực G 5 5 only if for every v K G v has a Hamilton path. có chu trình Hamilton khi và chỉ khi khi với mọi v K đồ thị G v có đường Hamilton. Từ khóa - đồ thị tách cực chu trình Hamilton đường Hamilton đồ Key words - split graph Hamilton cycle Hamilton path non- thị tách cực phi Hamilton tối đại bậc cực tiểu. hamiltonian split graph minimum degree. độ bền bằng 2 đều có chu trình Hamilton các tác giả 1. Đặt vấn đề Kratsch Lehel và Muller 6 đã nghiên cứu mối quan hệ Tất cả các đồ thị được nói tới trong bài báo này là những giữa độ bền với sự tồn .
