Maximum Girth Of Some Classes Of Sparse Graphs

Let G be an undirected connected graph.If graph G contains cycles,the girth of G is the length of a shortest cycle in graph G.If graph G is acyclic,the girth of G is infinite.In this thesis,we only study the girth of graphs with cycles.Denote by g(n,m)the maximum girth of an undirected connected graph of order n and size n+m.The main results of this thesis are as follows:1.When m=1,2,we give new proofs of the value of g(n,m)and characterize the corresponding extremal graphs;2.When m=3,4,5,6,7,we give lower and upper bounds for g(n,m)and characterize some extremal graphs;3.When m is a positive integer and n is some specific value related to m,the value of the maximum girth is determined and extremal graphs are characterized.For example:when n?7(mod 12)orn?10(mod 15)orn?13(mod 18),g(n,5)=(n+5)/3;4.For any m,we also give lower and upper bounds for g(n,m).