2-factors in $\frac{3}{2}$-tough maximal planar graphs
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866915366782894080 |
|---|---|
| author | Hao, Lili Ma, Hui Shan, Songling Yang, Weihua |
| author_facet | Hao, Lili Ma, Hui Shan, Songling Yang, Weihua |
| contents | The toughness of a graph $G$ is defined as the minimum value of $|S|/c(G-S)$ over all cutsets $S$ of $G$ if $G$ is noncomplete, and is defined to be $\infty$ if $G$ is complete. For a real number $t$, we say that $G$ is $t$-tough if its toughness is at least $t$. Followed from the classic 1956 result of Tutte, every more than $\frac{3}{2}$-tough planar graph on at least three vertices has a 2-factor. In 1999, Owens constructed a sequence of maximal planar graphs with toughness $\frac{3}{2}-\varepsilon$ for any $\varepsilon >0$, but the graphs do not contain any 2-factor. He then posed the question of whether there exists a maximal planar graph with toughness exactly $\frac{3}{2}$ and with no 2-factor. This question was recently answered affirmatively by the third author. This naturally leads to the question: under what conditions does a $\frac{3}{2}$-tough maximal planar graph contain a 2-factor? In this paper, we provide a sufficient condition for the existence of 2-factors in $\frac{3}{2}$-tough maximal planar graphs, stated as a bound on the distance between vertices of degree 3. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_00395 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | 2-factors in $\frac{3}{2}$-tough maximal planar graphs Hao, Lili Ma, Hui Shan, Songling Yang, Weihua Combinatorics The toughness of a graph $G$ is defined as the minimum value of $|S|/c(G-S)$ over all cutsets $S$ of $G$ if $G$ is noncomplete, and is defined to be $\infty$ if $G$ is complete. For a real number $t$, we say that $G$ is $t$-tough if its toughness is at least $t$. Followed from the classic 1956 result of Tutte, every more than $\frac{3}{2}$-tough planar graph on at least three vertices has a 2-factor. In 1999, Owens constructed a sequence of maximal planar graphs with toughness $\frac{3}{2}-\varepsilon$ for any $\varepsilon >0$, but the graphs do not contain any 2-factor. He then posed the question of whether there exists a maximal planar graph with toughness exactly $\frac{3}{2}$ and with no 2-factor. This question was recently answered affirmatively by the third author. This naturally leads to the question: under what conditions does a $\frac{3}{2}$-tough maximal planar graph contain a 2-factor? In this paper, we provide a sufficient condition for the existence of 2-factors in $\frac{3}{2}$-tough maximal planar graphs, stated as a bound on the distance between vertices of degree 3. |
| title | 2-factors in $\frac{3}{2}$-tough maximal planar graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2507.00395 |