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

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 .

• Toán học
• Đồ thị tách cực
• Chu trình Hamilton
• Đồ thị tách cực phi Hamilton tối đại
• Bậc cực tiểu
• Lý thuyết đồ thị
• Đồ thị 2 phần
• Đồ thị đầy đủ
• Đồ thị rỗng
• Đ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
• Bài giảng Lý thuyết đồ thị
• Giới thiệu Lý thuyết đồ thị
• Môn học Lý thuyết đồ thị
• Đại cương Lý thuyết đồ thị
• Hình thức thi Lý thuyết đồ thị
• tài liệu về lý thuyết đồ thị
• học lý thuyết đồ thị tốt
• phương pháp học lý thuyết đồ thị
• hàm trên đồ thị
• Đại cương về đồ thị
• Các mô hình đồ thị
• Thuật ngữ cơ bản của đồ thị
• Đường đi của đồ thị
• Sự liên thông đồ thị
• Biểu diễn đồ thị trên máy tính
• Sự đẳng cấu của đồ thị
• Phương pháp biểu diễn đồ thị
• Biểu diễn đồ thị bằng ma trận kề
• Đồ thị Euler
• Đồ thị Hamilton
• Kiểm tra đồ thị Hamilton
• Đơn đồ thị đặc biệt
• Đồ thị bánh xe
• Đồ thị con
• Mô hình đồ thị