Hamiltonicity of Cartesian products of trees with odd paths
A $\{P_2,P_3\}$-factor in a graph $G$ is a factor of $G$ in which every component is a path on two or three 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 and $n$ is a sufficiently large even integer. In this article we prove that, for every odd $n$, there exists a tree $T$ of maximum degree 4 that has a $\{P_2,P_3\}$-factor such that $T\Box P_n$ is not hamiltonian, thereby refuting a conjecture by Kao and Weng.
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2607.09270
curl -X POST /api/v1/records/arxiv/2607.09270/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2607.09270/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'