Pancyclicity of almost-planar graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912090215677952 |
|---|---|
| author | Adams, Santiago T. Kingan, S. R. |
| author_facet | Adams, Santiago T. Kingan, S. R. |
| contents | A non-planar graph is almost-planar if either deleting or contracting any edge makes it planar. A graph with $n$ vertices is pancyclic if it contains a cycle of every length from $3$ to $n$, and it is Hamiltonian if it contains a cycle of length $n$. A Hamiltonian path is a path of length $n$ and a graph with a Hamiltonian path between every pair of vertices is called Hamiltonian-connected. In 1990, Gubser characterized the class of almost-planar graphs. This paper explores the pancyclicity of these graphs. We prove that a $3$-connected almost-planar graph is pancyclic if and only if it has a cycle of length 3. Furthermore, we prove that a 4-connected almost-planar graph is both pancyclic and Hamiltonian-connected. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_21239 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Pancyclicity of almost-planar graphs Adams, Santiago T. Kingan, S. R. Combinatorics Combinatorics, Graph Theory A non-planar graph is almost-planar if either deleting or contracting any edge makes it planar. A graph with $n$ vertices is pancyclic if it contains a cycle of every length from $3$ to $n$, and it is Hamiltonian if it contains a cycle of length $n$. A Hamiltonian path is a path of length $n$ and a graph with a Hamiltonian path between every pair of vertices is called Hamiltonian-connected. In 1990, Gubser characterized the class of almost-planar graphs. This paper explores the pancyclicity of these graphs. We prove that a $3$-connected almost-planar graph is pancyclic if and only if it has a cycle of length 3. Furthermore, we prove that a 4-connected almost-planar graph is both pancyclic and Hamiltonian-connected. |
| title | Pancyclicity of almost-planar graphs |
| topic | Combinatorics Combinatorics, Graph Theory |
| url | https://arxiv.org/abs/2410.21239 |