A Note on Circumferences in \(k\)-Connected Graphs with Given Independence Number

Abstract

Fouquet and Jolivet conjectured that if \(G\) is a \(k\)-connected \(n\)-vertex graph with independence number \(\alpha \geq k \geq 2\), then \(G\) has circumference at least \( \frac{k(n+\alpha-k)}{\alpha} \). This conjecture was recently proved by \(O\), West, and Wu.
In this note, we consider the set of \(k\)-connected \(n\)-vertex graphs with independence number \(\alpha > k \geq 2\) and circumference exactly \( \frac{k(n+\alpha-k)}{\alpha} \). We show that all of these graphs have a similar structure.