TAILIEUCHUNG - Chu trình Hamilton trong đồ thị tách cực G = S (I hợp K, E) với deg(u) nhỏ hơn hoặc bằng 2 với mọi u thuộc I

Đồ thị G = (V ,E) được gọi là đồ thị tách cực nếu tồn tại phân hoạch V = I hợp K 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à S (I hợp K, E). 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. | 94 Lê Xuân Hùng 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 HAMILTON CYCLES IN SPLIT GRAPHS G = S (I K , E) WITH deg(u) 2 FOR ANY u I Lê Xuân Hùng Trường Đại học Tài nguyên và Môi trường Hà Nội; lxhung@ Tóm tắt - Đồ thị G = (V , E ) được gọi là đồ thị tách cực nếu tồn tại phân hoạch V = I K 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à S ( I K , E ) . 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. 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 G = S ( I K , E ) với I K và deg(u ) 2 với mọi u I . Chúng ta chứng minh được rằng đồ thị tách cực G có chu trình Hamilton khi và chỉ khi ' ' ' N ( I ) I với mọi I I và N I ( v ) 2 với mọi v K . Abstract - A graph G = (V , E ) is called a split graph if there exists a partition V = I K so that the subgraphs of G induced by I and K are empty and complete, respectively. We will denote such a graph by S ( I K , E ) . The notion of split graphs was introduced in 1977 by S. Foldes and P. L. Hammer. In this paper, we characterize Hamiltonian graphs in the class of split graphs G = S ( I K , E ) with I K and deg( u ) 2 for any u I . We prove that split graph G has Hamilton cycle if and only if ' ' ' N ( I ) I for any I I and N I ( v ) 2 for any v K . Từ khóa - đồ thị tách cực; chu trình Hamilton; đồ thị 2 phần; đồ thị đầy đủ; đồ thị rỗng. Key words - split graph; Hamilton cycle; bipartite graph; complete graph; empty graph. 1. Đặt vấn đề Tất cả các đồ thị được nói tới trong bài báo này là những đơn đồ thị hữu hạn, vô hướng, không có khuyên và không có cạnh bội. Nếu G là một đồ thị, thì V (G) (hoặc V ) được gọi là tập đỉnh và E(G) (hoặc E ) được gọi là tập cạnh. Tập hợp tất cả các đỉnh là hàng xóm của tập con S V (G) được ký

• Toán học
• Đồ thị tách cực
• Chu trình Hamilton
• Đồ thị 2 phần
• Đồ thị đầy đủ
• Đồ thị rỗng
• Đồ thị tách cực phi Hamilton tối đại
• Bậc cực tiểu
• Lý thuyết đồ thị
• Đa thức tô màu
• Đồ thị duy nhất tô màu
• Bài toán tô màu đồ thị
• Đồ thị duy nhất k tô màu danh sách
• Tô màu danh sách đỉnh
• Tô màu đỉnh