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 <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$T\Box P_n$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>T</mi> <mo>□</mo> <msub> <mi>P</mi> <mi>n</mi> </msub> </mrow> </math></EquationSource> </InlineEquation> be the Cartesian product of a tree T and a path on n vertices. Kao and Weng [<CitationRef CitationID="CR11">11</CitationRef>] proved that <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$T\Box P_n$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>T</mi> <mo>□</mo> <msub> <mi>P</mi> <mi>n</mi> </msub> </mrow> </math></EquationSource> </InlineEquation> is hamiltonian if T has a path factor, n is an even integer and <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$n\ge 4\Delta (T)-2$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mo>≥</mo> <mn>4</mn> <mi mathvariant="normal">Δ</mi> <mo stretchy="false">(</mo> <mi>T</mi> <mo stretchy="false">)</mo> <mo>-</mo> <mn>2</mn> </mrow> </math></EquationSource> </InlineEquation>. They conjectured that for every <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$\Delta \ge 3$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="normal">Δ</mi> <mo>≥</mo> <mn>3</mn> </mrow> </math></EquationSource> </InlineEquation> there exists a connected graph G of maximum degree <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$\Delta $</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="normal">Δ</mi> </math></EquationSource> </InlineEquation> which has a path factor, such that for every even <InlineEquation ID="IEq6"> <EquationSource Format="TEX">$n< 4\Delta -2$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mo><</mo> <mn>4</mn> <mi mathvariant="normal">Δ</mi> <mo>-</mo> <mn>2</mn> </mrow> </math></EquationSource> </InlineEquation> the product <InlineEquation ID="IEq7"> <EquationSource Format="TEX">$G\Box P_n$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>G</mi> <mo>□</mo> <msub> <mi>P</mi> <mi>n</mi> </msub> </mrow> </math></EquationSource> </InlineEquation> is not hamiltonian. In this article we prove this conjecture.

Hamiltonicity of Cartesian products of graphs

期刊论文
出版模式：

开放获取
发表日期：

2025年12月16日

查看全文

Irena Hrastnik Ladinek,
Ẑana Kovijanić Vukićević,
Tjaša Paj Erker,
Simon Špacapan

摘要

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$ $T □ P_{n}$ be the Cartesian product of a tree T and a path on n vertices. Kao and Weng [11] proved that $T\Box P_n$ $T □ P_{n}$ is hamiltonian if T has a path factor, n is an even integer and $n\ge 4\Delta (T)-2$ $n \geq 4 Δ (T) - 2$ . They conjectured that for every $\Delta \ge 3$ $Δ \geq 3$ there exists a connected graph G of maximum degree $\Delta $ $Δ$ which has a path factor, such that for every even $n< 4\Delta -2$ $n < 4 Δ - 2$ the product $G\Box P_n$ $G □ P_{n}$ is not hamiltonian. In this article we prove this conjecture.