On Extremal Problems Related To Cycle Lengths In Graphs

The cycle is the most essential and fundamental concept and object in graph theory,and the study of cycles has been one of the most important themes and driving forces in the development of graph theory.In this thesis,we focus on the interrelationship between the distribution of cycle lengths and some important graph invariants(including minimum degree,average degree,connectivity,chromatic number,etc.).Our results give tight extremal relations between the cycle length distribution and these invariants,and we address a series of open questions and conjectures in this field.The thesis is organized as follows:In Chapter 1,we briefly review the developments of problems related to cycle lengths in graphs.And we present our main results in this thesis.In Chapter 2,we discuss the cycles whose lengths differ by one or two in graphs.We prove that for any nonnegative integer k,except finitely many counterexamples,every graph with k vertices of degree less than three contains two cycles whose lengths differ by one or two,which resolves a earlier conjecture of Bondy and Vince.In Chapter 3,we prove the following statements by a unified approach(a result of admissible path between two vertices).1.Every graph G with minimum degree at least k+1 contains cycles of all even lengths modulo k;in addition,if G is 2-connected and non-bipartite,then it contains cycles of all lengths modulo k.2.Every 3-connected non-bipartite graph with minimum degree at leastk+1 contains k cycles of consecutive lengths.3.Every graph with chromatic number at least k+2 contains k cycles of consecutive lengths.In Chapter 4,we discuss some problems related to cycle lengths modulo a fixed integer,and we prove that for all k≥3,every k-connected graph contains a cycle of length zero modulo k,which solves a conjecture of Dean.In Chapter 5,we investigate the connection between average degree and k vertexdisjoint cycles of consecutive even lengths.Verstra?te conjectured every graph with average degree at least k2+3k+2 contains k vertex-disjoint cycles of consecutive even lengths.We prove this conjecture for k ≥19 when G is sufficiently large.In Chapter 6,we briefly introduce another work related to rainbow matching in hypergraphs.