Circumferences of k-connected graphs involving independence numbers

✍ Scribed by Guantao Chen; Zhiquan Hu; Yaping Wu

• Publisher: John Wiley and Sons
• Year: 2010
• Tongue: English
• Weight: 211 KB
• Volume: 68
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.20540

✦ Synopsis

Let G be a k-connected graph of order n, := (G) the independence number of G, and c(G) the circumference of G. Chvátal and Erdo ˝s proved that if ≤ k then G is hamiltonian. For ≥ k ≥ 2, Fouquet and Jolivet in 1978 made the conjecture that c(G) ≥ k(n+ -k) / . Fournier proved that the conjecture is true for ≤ 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 ≥ k, then c(G) ≥ (k(n+ -k) / )-((k -3)(k -4) / 2). Consequently, the conjecture of Fouquet and Jolivet holds for k = 4. In addition, we confirm the conjecture for = 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 (G -V

). 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 )∪V (D 2 ) ⊇ V (C 1 )∪V (C 2 ) and |V (D 1 )∩V (D 2 )| ≥ k. We show that the combination of the above two conjectures implies the conjecture of Fouquet and Jolivet.