{
  "id": "2211.03095",
  "version": "v1",
  "published": "2022-11-06T12:25:46.000Z",
  "updated": "2022-11-06T12:25:46.000Z",
  "title": "Cyclability, Connectivity and Circumference",
  "authors": [
    "Anish Hebbar",
    "Niranjan Balachandran"
  ],
  "categories": [
    "math.CO",
    "cs.DM"
  ],
  "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 \\geq 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 \\leq \\sqrt{n+3}$, $k$-cyclable graphs also have circumference $c(G) \\geq 2k$, and that this is best possible. Furthermore when $k \\leq \\frac{3n}{4} -1$, $c(G) \\geq k+2$, and for $k$-ordered graphs we show $c(G) \\geq \\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 \\geq 2(k^2+k)$ with $|E(G)| > \\binom{n-k}{2} + k^2$, then the graph is hamiltonian, and moreover the extremal graphs are unique.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2022-11-06T12:25:46.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "circumference",
      "cyclability",
      "connectivity",
      "connected graph",
      "extremal graphs"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}