Cyclability, Connectivity and Circumference

Abstract

In a graph $G$, a subset of vertices $S\subseteq V(G)$ is said to be cyclable if there is a cycle containing the vertices in some order. $G$ is said to be $k$-cyclable if any subset of $k\ge 2$ vertices is cyclable. If any $k$ \textit{ordered} vertices are present in a common cycle in that order, then the graph is said to be $k$-ordered. We show that when $k\le \sqrt{n+3}$, $k$-cyclable graphs also have circumference $c(G)\ge 2k$, and that this is best possible. Furthermore when $k\le \frac{3n}{4}-1$, $c(G)\ge k+2$, and for $k$-ordered graphs we show $c(G)\ge \min \{n,2k\}$. We also generalize a result by Byer et al. on the maximum number of edges in nonhamiltonian $k$-connected graphs, and show that if $G$ is a $k$-connected graph of order $n\ge 2(k^2+k)$ with $|E(G)|>\left(\genfrac{}{}{0ex}{}{n-k}{2}\right)+k^2$, then the graph is hamiltonian, and moreover the extremal graphs are unique.