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 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. [4] 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( {\begin{array}{c}n-k\\ 2\end{array}}\right) + k^2$, then the graph is hamiltonian, and moreover the extremal graphs are unique.