Some Problems On The Cycle Length On Graphs

Letn,r,tbe positive integers and j be nonnegative integer.A simple graph G of order n is said to be r-(d0,...,dt-1)-pancyclic graph if G contains exactly di(0?i?t-1)cycles of length r+tj+i satisfying r+tj+i?n and t is the period of di(0?i?t-1),j is the number of t repeats.A simple graph G of order n is said to be r-(d0,...,dt-1)-oddpancyclic(or bipancyclic)graph if G contains exactly di(0?i?t-1)cycles of length odd(or even)r+tj+i satisfying r+tj+i?n and tis the period of di(0?i?t-1),j is the number of t repeats.If ci,i=1,...,n is the number of cycles of length i,then the cycle length distribution of a graph G of order n is denoted by(c1,…,cn).The minimum possible edges of a graph G is denoted by g(a1,…,an),where ci?ai,i=1,...,nIn this thesis,we mainly consider some problems on the cycle length of graphs.The main results of this thesis are listed as follows1.We provide a construction for r-(d0,...,dt-1)-pancyclic graphs where d0?6·2?1,d1?6·2?1,d2=8·2?1,d3=6·2?1,t=4.Similar method also can be used to construct r-(d0,...,dt-1)-oddpancyclic(or bipancyclic)graphs for do=6·2 ?1,d1=8.2 ?1,d2=6·2?1,d2=6·2?1,t=4.Based on construction of r-(d0,...,dt-1)-pancyclic graphs,we obtain the bound of the smallest number of edges g(0,0,6,...,6),when r=32.When t=1,di=4,r=3,we get a necessary condition for(4)-pancyclic graphs.