Title: Ore-type conditions for existence of a jellyfish in a graph
Abstract: The famous Dirac's Theorem states that for each n ≥ 3, every n-vertex graph G with minimum degree δ(G) ≥ n/2 has a hamiltonian cycle. When δ< n/2, this cannot be guaranteed, but the existence of some other specific subgraphs can be provided. Chen, Ferrara, Hu, Jacobson and Liu proved that for n ≥ 56, every connected n-vertex graph G with δ(G) ≥ (n-2)/3 contains a spanning broom, i.e., a spanning tree obtained by joining the center of a star to an endpoint of a path. They also were looking for 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 talk 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) ≥ (2n-3)/3, then G has a spanning jellyfish. The bound is sharp for infinitely many n. One of the main ingredients of our proof is a modification of the Hopping Lemma due to Woodall from 1972. This is a joint work with Jaehoon Kim and Ruth Luo.