Long cycles in 3-cyclable graphs (Q1978141)

Let \(G\) denote a graph with \(n<\infty\) vertices, least valence \(\delta\), and independence number \(\alpha\). \(G\) is \(k\)-cyclable if given any \(k\)-set \(S\) of vertices, there exists a circuit in \(G\) through \(S\). Let \(c(G)\) denote the length of a longest circuit in \(G\). It is shown that if \(G\) has connectivity exactly 2, then \(c(G)\geq\min\{n,3\delta-2\}\), and this result is best possible. Also, if \(G\) is 3-connected, then \(c(G)\geq\min\{n,3\delta-3,n+\delta-\alpha\}\), whence if \(G\) is 3-cyclable, then the latter inequality also holds.