Spanning jellyfishes in graphs

Zoom Link

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. Chen,  Ferrara, Hu,   Jacobson and  Liu proved  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 tree obtained by joining the center of a star to an endpoint of a path. They also were looking for 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 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) \geq \frac{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.

Please report video problems to itsupport@slmath.org.

See more of our Streaming videos on our main VMath Videos page.