Circumferences of k-Connected Graphs Involving Independence Numbers

Let G be a k-connected graph of order n, alpha: = alpha(G) the independence number of G, and c(G) the circumference of G. Chvatal and Erdos proved that if alpha <= k then G is hamiltonian. For alpha >= k >= 2, Fouquet and Jolivet in 1978 made the conjecture that c(G) >= k(n+alpha-k)/alpha. Fournier proved that the conjecture is true for alpha <= k+2 or k=2 in two different papers. Manoussakis recently proved that the conjecture is true for k=3. We prove that if G is a k-connected graph, k >= 4, of order n and independence number alpha >= k, then c(G)>=(k(n+alpha-k)/alpha)-((k-3)(k-4)/2). Consequently, the conjecture of Fouquet and Jolivet holds for k=4. In addition, we confirm the conjecture for alpha = k+3. Inspired by a result of Kouider, we conjecture that, for every graph G and any two distinct vertices u and v, there is a u-v path P such that alpha(G-V(P))<=alpha(G)-1 unless V(G) have a nontrivial partition V(1)boolean OR V(2) satisfying alpha(G)=alpha(G[V(1)])+alpha(G[V(2)]). In this paper, we obtain a partial result regarding this conjecture. Let G be a k-connected graph and k >= 2. While studying the intersection of longest cycles, J. Chen et al. conjectured that, for any two cycles C(1) and C(2) of G, there are two cycles D(1) and D(1) such that V(D(1))boolean OR V(D(2))superset of V(C(1))boolean OR V(C(2)) and vertical bar V(D(1))boolean AND V(D(2))vertical bar >= k. We show that the combination of the above two conjectures implies the conjecture of Fouquet and Jolivet. (C) 2010 Wiley Periodicals, Inc. J Graph Theory 68: 55-76, 2011