{
  "id": "2404.00811",
  "version": "v2",
  "published": "2024-03-31T21:58:17.000Z",
  "updated": "2024-10-14T17:38:48.000Z",
  "title": "Ore-type conditions for existence of a jellyfish in a graph",
  "authors": [
    "Jaehoon Kim",
    "Alexandr Kostochka",
    "Ruth Luo"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "The famous Dirac's Theorem states that for each $n\\geq 3$ every $n$-vertex graph $G$ with minimum degree $\\delta(G)\\geq n/2$ has a hamiltonian cycle. When $\\delta(G)< n/2$, this cannot be guaranteed, but the existence of some other specific subgraphs can be provided. Gargano, Hell, Stacho and Vaccaro proved that every connected $n$-vertex graph $G$ with $\\delta(G)\\geq (n-1)/3$ contains a spanning {\\em spider}, i.e., a spanning tree with at most one vertex of degree at least $3$. Later, Chen, Ferrara, Hu, Jacobson and Liu proved the stronger (and exact) result that for $n\\geq 56$ every connected $n$-vertex graph $G$ with $\\delta(G)\\geq (n-2)/3$ contains a spanning {\\em broom}, i.e., a spanning spider obtained by joining the center of a star to an endpoint of a path. They also showed that a $2$-connected graph $G$ with $\\delta(G)\\geq (n-2)/3$ and some additional properties contains a spanning {\\em jellyfish} which is a graph obtained by gluing the center of a star to a vertex in a cycle disjoint from that star. Note that every spanning jellyfish contains a spanning broom. The goal of this paper is to prove an exact Ore-type bound which guarantees the existence of a spanning jellyfish: We prove that if $G$ is a $2$-connected graph on $n$ vertices such that every non-adjacent pair of vertices $(u,v)$ satisfies $d(u) + d(v) \\geq \\frac{2n-3}{3}$, then $G$ has a spanning jellyfish. As corollaries, we obtain strengthenings of two results by Chen et al.: a minimum degree condition guaranteeing the existence of a spanning jellyfish, and an Ore-type sufficient condition for the existence of a spanning broom. The corollaries are sharp for infinitely many $n$. One of the main ingredients of our proof is a modification of the Hopping Lemma due to Woodall.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2024-10-14T17:38:48.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C07",
      "05C38",
      "05C35"
    ],
    "keywords": [
      "ore-type conditions",
      "vertex graph",
      "spanning jellyfish",
      "spanning broom",
      "additional properties contains"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}