Degree sum conditions for the circumference of 4-connected graphs

We denote the order, the independence number, the connectivity and the minimum degree sum of independent four vertices of a graph G by n(G), alpha(G), K(G) and sigma(4)(G), respectively. The circumference of a graph G, denoted by c(G), is the length of a longest cycle in G. We call a cycle C of a graph G a D-k-cycle if the order of each component of G - V(C) is at most k - 1. Our goal is to accomplish the proof of the statement that if G is a 4-connected graph, then c(G) >= min{sigma(4)(G) - K(G) - alpha(G) + 1, n(G)}. In order to prove this, we consider three conditions for the construction of the outside of a longest cycle: (i) If G is a 3-connected graph and every longest cycle of G is a D-2-cycle, then c(G) >= min{sigma(4)(G) - K(G) - alpha(G) +1, n (G)} (ii) If G is a 3-connected graph and every longest cycle is a D-3-cycle and some longest cycle is not a D-2-cycle, then c(G) >= sigma(4)(G) - K(G) - 4. (iii) If G is a 4-connected graph and some longest cycle is not a D-3-cycle, then c(G) >= sigma(4)(G) - 8. For each condition, the lower bound of the circumference is sharp. (C) 2014 Elsevier B.V. All rights reserved.