On a Conjecture of Fan Concerning Average Degrees and Long Cycles

Source abstract

In this paper, we prove the following result: Let k be an integer with k≥5. Let C be a cycle in a graph G, and let H be a component of G−C. Suppose that C is locally longest with respect to H, and H is locally k-connected to C, | V(H) |≥k−1, δ(H)≥⌊ (k−1)/2 ⌋, and H is 3-connected. Let r=(∑x∈V(H)degG(x))/|V(H)|. Then l(C)≥k(r+2−k), with equality only if r is an integer and either H is a complete graph of order r+1−k and every vertex of H has the same k neighbours on C, or H is a complete graph of order k−1 and every vertex of H has the same r+2−k neighbours on C.