Ore-type conditions for existence of a jellyfish in a graph
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866913543831420928 |
|---|---|
| author | Kim, Jaehoon Kostochka, Alexandr Luo, Ruth |
| author_facet | Kim, Jaehoon Kostochka, Alexandr Luo, Ruth |
| contents | The famous Dirac's Theorem states that for each $n\geq 3$ every $n$-vertex graph $G$ with minimum degree $δ(G)\geq n/2$ has a hamiltonian cycle. When $δ(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 $δ(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 $δ(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 $δ(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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_00811 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Ore-type conditions for existence of a jellyfish in a graph Kim, Jaehoon Kostochka, Alexandr Luo, Ruth Combinatorics 05C07, 05C38, 05C35 The famous Dirac's Theorem states that for each $n\geq 3$ every $n$-vertex graph $G$ with minimum degree $δ(G)\geq n/2$ has a hamiltonian cycle. When $δ(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 $δ(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 $δ(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 $δ(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. |
| title | Ore-type conditions for existence of a jellyfish in a graph |
| topic | Combinatorics 05C07, 05C38, 05C35 |
| url | https://arxiv.org/abs/2404.00811 |