Ore‐Type Conditions for Existence of a Jellyfish in a Graph

ABSTRACT The famous Dirac's theorem states that for each every ‐vertex graph with minimum degree has a Hamiltonian cycle. When , this cannot be guaranteed, but the existence of some other specific subgraphs can be provided. Gargano, Hammar, Hell, Stacho, and Vaccaro proved that every connected ‐vertex graph with contains a spanning spider , that is, 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 every connected ‐vertex graph with contains a spanning broom , that is, 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 with and some additional properties contains a spanning 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 is a 2‐connected graph on vertices such that every nonadjacent pair of vertices satisfies , then 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 . One of the main ingredients of our proof is a modification of the Hopping Lemma due to Woodall.