Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2408.06770 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909286168264704 |
|---|---|
| author | Ladinek, Irena Hrastnik Vukićević, Žana Kovijanić Erker, Tjaša Paj Špacapan, Simon |
| author_facet | Ladinek, Irena Hrastnik Vukićević, Žana Kovijanić Erker, Tjaša Paj Špacapan, Simon |
| contents | A path factor in a graph $G$ is a factor of $G$ in which every component is a path on at least two vertices. Let $T\Box P_n$ be the Cartesian product of a tree $T$ and a path on $n$ vertices. Kao and Weng proved that $T\Box P_n$ is hamiltonian if $T$ has a path factor, $n$ is an even integer and $n\geq 4Δ(T)-2$. They conjectured that for every $Δ\geq 3$ there exists a graph $G$ of maximum degree $Δ$ which has a path factor, such that for every even $n< 4Δ-2$ the product $G\Box P_n$ is not hamiltonian. In this article we prove this conjecture. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_06770 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Hamiltonicity of Cartesian products of graphs Ladinek, Irena Hrastnik Vukićević, Žana Kovijanić Erker, Tjaša Paj Špacapan, Simon Combinatorics A path factor in a graph $G$ is a factor of $G$ in which every component is a path on at least two vertices. Let $T\Box P_n$ be the Cartesian product of a tree $T$ and a path on $n$ vertices. Kao and Weng proved that $T\Box P_n$ is hamiltonian if $T$ has a path factor, $n$ is an even integer and $n\geq 4Δ(T)-2$. They conjectured that for every $Δ\geq 3$ there exists a graph $G$ of maximum degree $Δ$ which has a path factor, such that for every even $n< 4Δ-2$ the product $G\Box P_n$ is not hamiltonian. In this article we prove this conjecture. |
| title | Hamiltonicity of Cartesian products of graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2408.06770 |