tailieunhanh - Báo cáo toán học: "A Note on Maximal Nonhamiltonian Burkard–Hammer Graphs"

Đồ thị G = (V, E) được gọi là một đồ thị phân chia nếu có tồn tại một phân vùng V = I ∪ K như các subgraphs G [I] và G [K] G gây ra bởi tôi và K là trống rỗng, và hoàn thành đồ thị,tương ứng. | Vietnam Journal of Mathematics 34 4 2006 397-409 Viet n a m J o u r n a I of MATHEMATICS VAST 2006 A Note on Maximal Nonhamiltonian Burkard-Hammer Graphs Ngo Dac Tan Institute of Mathematics 18 Hoang Quoc Viet Road 10307 Hanoi Vietnam .th. Received February 22 2006 Abstract. A graph is called a split graph if there exists a partition such that the subgraphs and of induced by and are empty and complete graphs respectively. In 1980 Burkard and Hammer gave a necessary condition for a split graph with to be hamiltonian. We will call a split graph with satisfying this condition a Burkard-Hammer graph. Further a split graph is called a maximal nonhamiltonian split graph if is nonhamiltonian but is hamiltonian for every where and . In an earlier work the author and lamjaroen have asked whether every maximal nonhamiltonian Burkard-Hammer graph with the minimum degree where possesses a vertex adjacent to all vertices of and whether every maximal nonhamiltonian Burkard-Hammer graph with where and possesses a vertex with exactly neighbors in . The first question and the second one have been proved earlier to have a positive answer for and respectively. In this paper we give a negative answer both to the first question for all and to the second question for all . 2000 Mathematics Subject Classification 05C45. Keywords Split graph Burkard-Hammer condition Burkard-Hammer graph hamiltonian graph maximal nonhamiltonian split graph. 1. Introduction 398 Ngo Dac Tan . . W . G G . . G. split graph. .complete split graph. .Burkard-Hammer condition. . Burkard-Hammer graph . . maximal nonhamiltonian split graph. . . . Note on Maximal Nonhamiltonian Burkard-Hammer Graphs 399 2. Preliminaries . bipartite subgraph of induced by . and G j j. J. . . . G . . .G G . . . . . .G G G 0 . . . . G . .1 . . . . . . G 1 11 r G r r r r G G . G J J 1 . Bz __J G J J J L-component J I J G 1. . G . I . I. Theorem 1. a split graph with. If is hamiltonian then rz .