Videos

Introductory Workshop - Graph Theory: Extremal, Probabilistic and Structural: Spanning jellyfishes in graphs

February 14, 2025
Keywords:
  • extremal graph theory
  • random graphs
  • probabilistic methods
  • structural graph theory
  • Ramsey theory
MSC:
  • 05C35 - Extremal problems in graph theory [See also 90C35]
  • 05C55 - Generalized Ramsey theory [See also 05D10]
  • 05C75 - Structural characterization of families of graphs
  • 05C80 - Random graphs (graph-theoretic aspects) [See also 60B20]
  • 05D40 - Probabilistic methods in extremal combinatorics
  • including polynomial methods (combinatorial Nullstellensatz
  • etc.)
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. 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.