A sufficient condition for cubic 3-connected plane bipartite graphs to be hamiltonian
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916230253772800 |
|---|---|
| author | Florek, Jan |
| author_facet | Florek, Jan |
| contents | Barnette's conjecture asserts that every cubic $3$-connected plane bipartite graph is hamiltonian. Although, in general, the problem is still open, some partial results are known. In particular, let us call a face of a plane graph big (small) if it has at least six edges (it has four edges, respectively). Goodey proved for a $3$-connected bipartite cubic plane graph $P$, that if all big faces in $P$ have exactly six edges, then $P$ is hamiltonian. In this paper we prove that the same is true under the condition that no face in $P$ has more than four big neighbours. We also prove, that if each vertex in $P$ is incident both with a small and a big face, then~$P$ has at least $2^{k}$ different Hamilton cycles, where $k = \left\lceil\frac{|B|-2}{4Δ(B) - 7}\right\rceil$, $|B|$ is the number of big faces in $P$ and $Δ(B)$ is the maximum size of faces in $P$. 15 pages |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2309_09578 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | A sufficient condition for cubic 3-connected plane bipartite graphs to be hamiltonian Florek, Jan Combinatorics 05C45, 05C10, 05C05 Barnette's conjecture asserts that every cubic $3$-connected plane bipartite graph is hamiltonian. Although, in general, the problem is still open, some partial results are known. In particular, let us call a face of a plane graph big (small) if it has at least six edges (it has four edges, respectively). Goodey proved for a $3$-connected bipartite cubic plane graph $P$, that if all big faces in $P$ have exactly six edges, then $P$ is hamiltonian. In this paper we prove that the same is true under the condition that no face in $P$ has more than four big neighbours. We also prove, that if each vertex in $P$ is incident both with a small and a big face, then~$P$ has at least $2^{k}$ different Hamilton cycles, where $k = \left\lceil\frac{|B|-2}{4Δ(B) - 7}\right\rceil$, $|B|$ is the number of big faces in $P$ and $Δ(B)$ is the maximum size of faces in $P$. 15 pages |
| title | A sufficient condition for cubic 3-connected plane bipartite graphs to be hamiltonian |
| topic | Combinatorics 05C45, 05C10, 05C05 |
| url | https://arxiv.org/abs/2309.09578 |