R-(k)-pancyclic Graphs And Related Extremal Problems On The Cycle Length Distribution Of Graphs

Let n,r,k be positive integers where 3 ￡r ￡n and k 32. A graph G of order n is said to be r -(k) - pancyclic if G contains exactly k t - cycles for all t satisfying r ￡t ￡n. In particular, we call r -(k) - pancyclic graphs for r =3 by (k) - pancyclic graphs. A graph G of order n is said to be r -(k) - oddpancyclic(or bipancyclic) if G contains exactly k t - cycles for any odd(or even)t ?{r,K,n}. The cycle length distribution(CLD) of a graph of order n is ( )1 2,,,nc c Lc,whereic is the number of cycles of length i,for i =1,2,K,n.For an integer sequence1 2(,,,)na a Ka, we consider the problem of characterizing a graph G with ( ) ( )1 2,,,nCLD G =c c Kc such thati ic 3a for i =1,2,K,n and G has the minimum possible number of edges.This number is denoted by( )1 2,,,ng a a La.In this thesis, we mainly consider r -(k) - pancyclic graphs and related extremal problems on the cycle length distribution of graphs.The main results of this thesis are listed as follows:1、We provide a construction for r -(k) - pancyclic graphs, where k2m=, mN*?.Similar method can be used to construct r-(k)-oddpancyclic(or bipancyclic) graphs for k2m= and r -(k) - pancyclic graphs for1k3m= or233 2mm, where1 2 3m,m,m,mN*?;2、Based on the constrution of r-(k)-pancyclic graphs, we construct a class of graphs with cycle length distribution ( )1 20,0,,,,na a Ka, whereia 3k, i =1,2,K,n, k =2,3,4, and give the upper and lower bounds for g(0,0,k,L,k), respectively;3、We discuss r -(3) - pancyclic graphs for r =3, that is (3)- pancyclic graphs, andgive some necessary conditions for (3) - pancyclic graphs.