Degree Conditions For Balanced Multipartite Graphs To Be Hamiltonian

The hamiltonian cycle problem for undirected graphs is a graph theory problem with an ancient history.However,up to now,there is no sufficient necessary condition for the existence of a hamiltonian cycle for an undirected graph.The research on it mainly focuses on finding sufficient conditions for the existence of hamiltonian cycles,and the sufficient conditions focus on the degree conditions.Many scholars have studied the degree conditions for hamiltonian cycles of general undirected graphs.In particular,the Fan-type condition is an important degree condition for hamiltonian cycles of undirected graphs.In recent years,the Fan-type condition of hamiltonian cycles in balanced bipartite graphs has attracted much attention,but it is still very imperfect.In this paper,we study the Fan-type condition for the existence of a hamiltonian cycle in a balanced bipartite graph,discussing the bipancyclicity of this condition,the existence of a hamiltonian cycle passing through every edge of a perfect matching under the degree condition,and the degree sum condition for the existence of hamiltonian cycles of balanced k-partite graphs.The thesis consists of three Chapters.Chapter 1 is the preface.The basic concepts and application background are introduced.And the main content of this thesis is proposed.In Chapter 2,we study the degree condition for the existence of a hamiltonian cycle for a balanced bipartite graph.In 1996,Gao Taiping and Yang Aimin introduced Fan-type condition in balanced bipartite graphs of order 2n and proved balanced bipartite graphs that any two vertices x and y with distance 2 satisfing max{d(x),d(y)}≥n/2+1 are hamiltonian.In 2018,Wang Miao and Liu Yan improved the above theorem to n+1/2.In this chapter,we first characterize extremal graphs of the above condition and prove that balanced bipartite graphs of all except six extremal graphs are hamiltonian.Secondly,we prove that balanced bipartite graphs are bipancyclic under the above condition with the exception of one extremal graph.From these two conclusions we can also obtain a balanced bipartite graph that for any two vertices x and y with distance 2 satisfying d(x)+d(y)=n is hamiltonian with three exceptions.A balanced bipartite graph that for any two vertices x and y in with distance 2 satisfying d(x)+d(y)≥n+1 is bipancyclic with one exception.In 2018,Wang Miao and Liu Yan proved a balanced bipartite graph of order 2n that any two vertices x and y with distance 2 of satisfying max{d(x),d(y)}≥ n contains a hamiltonian cycle passing through every edge of a perfect matching.In this chapter,we will show that a balanced bipartite graph for any two vertices x and y with distance 2 satisfying d(x)+d(y)≥n+2 contains a hamiltonian cycle passing through every edge of a perfect matching.In Chapter 3,we study the hamiltonicity of balanced k-partite graphs for the degree sum condition under every pair of nonadjacent vertices u and v which are belong to different partite sets.In 1997,Chen Guantao et al.gave degree sum conditions for the the existence of a hamiltonian cycle for balanced k-partite graphs of order n,and proposed balanced kpartite graphs that any two nonadjacent vertices u and v of different partite sets satisfying the condition d(u)+d(v)>2(n/2+n/2[k+1/2]-n/k)are hamiltonian.In this chapter,we will improve the lower bound of the above degree sum condition when n is odd.The bound is improved to d(u)+d(v)≥2([n/2]+[n+2/2[k+1/2]]-n/k).