JET  67
HAMILTONICITY OF CERTAIN CARTESI-
AN PRODUCTS OF GRAPHS
HAMILTONSKOST KARTEZIČNEGA 
PRODUKTA GRAFOV
Tjaša Paj Erker
1ℜ
Keywords: Hamiltonicity, Cartesian product, path factor
Abstract
A graph is Hamiltonian if it contains a spanning cycle. In this paper, we examine the hamiltonicity 
of the Cartesian product of a tree with a path. We offer sufficient conditions for the Cartesian 
product of a tree with a path to be Hamiltonian.
Povzetek
Graf je Hamiltonov, če vsebuje cikel, ki gre skozi vsako vozlišče natanko enkrat. V tem članku 
preučujemo hamiltonskost kartezičnega produkta drevesa in poti. Podamo zadostne pogoje, da 
bo kartezični produkt drevesa in poti Hamiltonov.
1 INTRODUCTION
A Hamiltonian path or traceable path is a path that visits each vertex of the graph exactly once. 
If there exists a Hamiltonian path in G, then G is referred to as traceable, and a graph is Hamilto-
nian if it contains a spanning cycle. In this article, we consider the hamiltonicity of the Cartesian 
product of two graphs. Our goal is to investigate the necessary and sufficient conditions for the 
Cartesian product to be Hamiltonian. We summarise some previous results and provide new 
ones. Certain results are related to those obtained in [2, 4].
JET Volume 15 (2022) p.p. 67-72
Issue 1, June 2022
Type of article: 1.01 
www.fe.um.si/si/jet.html
 
ℜ Corresponding author: Tjaša Paj Erker, University of Maribor, FME, Smetanova 17, 2000 Maribor, Slovenia. e-mail: 
tjasa.paj@um.si
1
 University of Maribor, FME, Smetanova 17, 2000 Maribor, Slovenia
Tjaša Paj Erker
Hamiltonskost kartezičnega produkta grafov

68 JET 68 JET
Tjaša Paj Erker JET Vol. 15 (2022)
Issue 1
Let G = (V(G), E(G)) be a graph with vertex set V(G) and the edge set E(G). The number of vertices 
in V(G) is the order of G. The degree of a vertex v is denoted by degG(v). The maximum degree 
in G is denoted by ∆(G). The number of isolated vertices of G is denoted by i(G). Let Pn denote 
a path of order n and Cn the cycle of order n. For convenience, we write V(Pn) = {1, 2,…,n} and 
E(P
n
) = {i(i + 1)|i = 1, 2,…, n — 1}. An end-vertex of G is a vertex of degree 1 in G. A path factor of 
a graph G is a spanning subgraph of G such that each component of the spanning subgraph is a 
nontrivial path. A graph has a {P2, P3}-factor if it has a spanning subgraph such that each compo-
nent is isomorfic to P2 or P3.
Lemma 1.1 ([4]) A graph G has a path factor if and only if G has a {P2, P3}-factor.
If each component in a {P2, P
3
}-factor is isomorfic to P
2
, the path factor is called perfect matching. 
The number of components of a graph G is denoted by c(G). A graph G is t-tough (t ϵ ℝ) if |S| > 
t∙ c(G \ S) for every subset S ⊆ V(G) with c(G \ S) > 1.
Let G = (V(G),E(G)) and H = (V(H), E(H)) be graphs. The Cartesian product of G and H is the graph 
G□H defined by V(G□H) = V(G) x V(H), where (x
1
, y
1
)(x
2
,y
2
) is an edge in G□H if x
1
 = x
2
 and y
1
y
2 
ϵ 
E(H), or x
1
x
2
 ϵ E(G), and y
1
 = y
2
. The graphs G and H are termed factors of the product. For an x ϵ 
V(G), the H-layer H
x
 is the set H
x
 = {(x, y) |y ϵ V(H)}.
2 CARTESIAN PRODUCT OF A TREE WITH A PATH
In this section we deal with Cartesian products of a tree with a path, i.e., we consider T□Pn, for 
n ≥ 4 even.
Proposition 2.1 ([3]) Let G and H be both of odd order. If both G and H are bipartite, then G□H is 
not Hamiltonian.
Notice that when the order of T and n is both odd, the T□Pn is not Hamiltonian by Proposition 
2.1, so we will focus on even paths. The lemma below is from [1].
Theorem 2.2 ([1]) Let T be a tree with ∆(T) ≥ 2 and Cn a cycle of order n. Then T□Cn is Hamiltonian 
if and only if ∆(T) ≤ n.
In [4], the authors showed that in the above theorem, T□Cn cannot be replaced by T□Pn. They 
give an example of a tree such that n = ∆(T) + 1 and T□Pn is not Hamiltonian, proving that for a 
tree T
1
 with the vertex set V(T
1
) = {1, 2, 3, 4, 5, 6, 7, 8} and the edge set E(T
1
) = {12, 23, 34, 45, 26, 
37, 48}, the graph T
1
□P
4
 is not Hamiltonian.
From the figure below we can see that T
1
□P
6
 is Hamiltonian. Therefore, we are interested in oth-
er examples of when this is possible.

JET  69
Hamiltonskost kartezičnega produkta grafov
 Hamiltonicity of certain cartesian products of graphs 3 
   
---------- 
Notice that when the order of T and n is both odd, the T �P
n
 is not Hamiltonian by Proposition 
2.1, so we will focus on even paths. The lemma below is from [1]. 
Theorem 2.2 ([1]) Let T be a tree with ∆(T) 	 ≥ 2 and C
n
 a cycle of order n. Then T �C
n
 is 
Hamiltonian if and only if ∆(T) 	 ≤ n.
In [4], the authors showed that in the above theorem, T �C
n
 cannot be replaced by T �P
n
. They 
give an example of a tree such that n = ∆(T) 	+ 1 and T �P
n
 is not Hamiltonian, proving that for a 
tree T
1
 with the vertex set V(T
1
) = {1, 2, 3, 4, 5, 6, 7, 8} and the edge set E(T
1
) = {12, 23, 34, 45, 
26, 37, 48}, the graph T
1
�P
4
 is not Hamiltonian. 
From the figure below we can see that T
1
�P
6
 is Hamiltonian. Therefore, we are interested in 
other examples of when this is possible. 
 
Figure 1: The Hamiltonian cycle in T
1
□P
6
In [4], the following result is proven.
Proposition 2.3 ([4]) Let H be a connected bipartite graph. Let n be an even integer and n ≥ 4 ∆(H) 
— 2. The following three statements are equivalent: (i) H□P
n
 is Hamiltonian; (ii) H□P
n
 is 1-tough; 
(iii) H has a path factor.
Motivated by the example above (Figure 1), we will be interested in examples of such trees T, 
for which the condition n ≥ 4∆ (H) — 2 in proposition 2.3 is not fulfilled, yet T□P
n
 is Hamiltoni-
an.
Proposition 2.4 ([4]) Let T be a tree with perfect matching and n be a positive integer. The fol-
lowing three statements are equivalent: (i) T□P
n
 is Hamiltonian; (ii) T□P
n
 is 1-tough; (iii) n ≥ ∆ (T).
Let T be a tree with {P
2
, P
3
}-factor F. We define the type of a vertex v with respect to F as follows:
• v has type EPL if v is the left endpoint of a P
3
 in F,
• v has type EPR if v is the right endpoint of a P
3
 in F,
• v has type M if v is the middle vertex of a P
3
 in F,
• v has type EP2 if v is a vertex of P
2
 in F.
Theorem 2.5 Suppose that T has a {P
2
, P3}-factor F and n is an even integer. If degT (x) ≤ (n+2)/2 
for every x of type M in F , degT (x) ≤ n/2 for every x of type EP2 in F and degT(x) + degT(y) ≤ (n+2)/2 
for every x, y of type EPL and EPR on every component in F isomorfic to P3, then T□Pn contains a 
Hamiltonian cycle.
Proof. Let F be a {P
2
, P
3
}-factor which satisfies the conditions in the theorem. If each component 
in F is isomorfic to P
2
, then T□Pn by proposition 2.4 contains a Hamiltonian cycle, since every 
vertex x in T has type EP2 and therefore degT(x) ≤ ∆(T) ≤ n/2 ≤ n.
So, we can assume that there exist a component isomorfic to P
3
.
First, we define the standard Hamiltonian cycle for P3□Pn and for P
2
□P
n
.
For {x, y, z} ϵ V(P
3
), {xy, yz} ϵ E(P
3
) and an even n, we define the set {(x, 1)(y, 1)}U {(y, 2i–1)(z, 
2i–1), (z, 2i–1)(z, 2i), (z, 2i)(y, 2i)|1 ≤ i ≤ n/2} U {(y, 2i)(y, 2i + 1)|1 ≤ i ≤ (n-2)/2} U {(y,n)(x,n)} 
U {(x,i)(x,i + 1)|1 ≤ i < n} of edges in P
3
□P
n
 as the standard Hamiltonian cycle for P3□Pn (see 
Figure 2 (left)).
For {u, v} ϵ V(P
2
), we define the set {(u, 1)(v, 1)} U {(v, i)(v, i + 1)|1 ≤ i ≤ n} U {(u, i)(u, i+1) |1 ≤ i < n} 
U {(u, n)(v, n)} of edges in P
2
□P
n
 as the standard Hamiltonian cycle for P
2
□P
n
 (see Figure 2 (right)).

70 JET 70 JET
Tjaša Paj Erker JET Vol. 15 (2022)
Issue 1
Notice that there are (n-2)/2 vertical edges on every P
n
-layer that correspond to a vertex y ϵ F 
of type M on the standard Hamiltonian cycle P3□Pn and that there are n/2 vertical edges on 
every P
n
-layer that correspond to a vertex y ϵ F of type EPR on the standard Hamiltonian cycle 
P3□Pn.
Figure 2: The standard Hamiltonian cycle for P3□Pn and for P2□Pn
We now use a recursive construction to reach a Hamiltonian cycle in T□Pn. We start with the 
standard Hamiltonian cycle for C’ = C1□Pn of initially chosen component C
1 
in F. Let C
2
 be a com-
ponent in F such that there is a vertex y ϵ C
2
 adjacent with a vertex x ϵ C
1
 (note that xy ϵ E(T)) 
and let C” = C2□Pn be a standard Hamiltonian cycle as described above. We can join such two 
standard cycles C’ and C” with cycle C’’’ with vertex set V (C’’’) = V (C’) U V (C’’) and edge set E(C’’’) 
as described below.
We distinguish several cases:
(i) C
1
 and C
2
 are isomorfic to P
2
We can join cycles C’ and C” with cycle C’” with edge set E(C’”) = ((E(C’) U E(C”)) \ {(x, i)(x, i 
+1), (y, i)(y, i + 1)}) U {(x, i)(y, i), (x, i + 1)(y, i + 1)} for every i = 1, 2, …, n–1 (see Figure 3 (a)).
(ii) C 
1
 is isomorfic to P
2
 and C
2
 is isomorfic to P3 (or vice-versa).
If y has type M, we can join such cycles C’ and C” with cycle C’” with edge set E(C’”) = ((E(C’) 
U E(C”)) \ {(x, 2i)(x, 2i + 1), (y, 2i)(y, 2i + 1)}) U {(x, 2i)(y, 2i), (x, 2i + 1)(y, 2i + 1)} for every i = 
1,2,…, (n-2)/2 (see Figure 3 (b)).
If y has type EPR (or EPL), we can join cycles C’ and C” with cycle C’” with edge set E(C’”) = 
((E(C’) U E(C”)) \ {(x, 2i–1)(x, 2i), (y, 2i–1)(y, 2i)}) U {(x, 2i -1)(y, 2i–1), (x, 2i)(y, 2i)} for every 
i = 1, 2,…, n/2 (see Figure 3 (c)).

JET  71
Hamiltonskost kartezičnega produkta grafov
Figure 3: Joining standard cycles C’=C1□Pn and C’’=C2□Pn for P2□Pn where C1 is isomorfic to 
P2
(iii) C
1
 and C
2
 are isomorfic to P
3
.
If x and y have type M, we can join cycles C’ and C” with cycle C’” with edge set E(C’”) = 
((E(C’) U E(C”)) \ {(x, 2i)(x, 2i + 1), (y, 2i)(y, 2i + 1)}) U {(x, 2i)(y, 2i), (x, 2i + 1)(y, 2i + 1)} for 
every i = 1, 2,…, (n-2)/2 (see Figure 4 (a)).
If x and y have type EPR (or EPL), we can join cycles C’ and C” with cycle C’” with edge set 
E(C’”) = ((E(C’) U E(C”)) \ {(x, 2i–1)(x, 2i), (y, 2i–1)(y, 2i)}) U {(x, 2i–1)(y, 2i–1), (x, 2i)(y, 2i)} for 
every i = 1, 2,…, n/2 (see Figure 4 (b)).
If x has type M and y has type EPL, we can join such two standard cy cles C’ and C” with cycle 
C’” with edge set ((E(C’) U E(C”)) \ {(x, 2i)(x, 2i + 1), (y, 2i)(y, 2i+1)})U{(x, 2i)(y, 2i), (x, 2i+1)(y, 
2i+1)} for every i = 1, 2,…, (n-2)/2 (see Figure 4 (c)).
Figure 4: Joining standard cycles C’=C1□Pn and C’’=C2□Pn for P2□Pn where C1 is isomorfic to 
P3
If x has type M and y has type EPR, we reshape the standard Hamiltonian cy cle C”= P
3
□Pn into 
C
ℜ . Denote y = y
3
 and {y
1
,y
2
,y
3
} ϵ V(P
3
) where {y
1
y
2
, y
2
y
3
} ϵ E(P
3
). Define, C
ℜ = (C''\{(y
1
, 2i)(y
1
, 2i+1), 
(y
2
,2i)(y
3
,2i), (y
2
,2i+1)(y
3
,2i + 1)})U{(y1, 2i)(y
2
, 2i), (y
1
, 2i + 1)(y
2
,2i + 1), (y
3
,2i)(y
3
,2i + 1)} for some 

72 JET 72 JET
Tjaša Paj Erker JET Vol. 15 (2022)
Issue 1
i = 1, 2,…, (n-2)/2 (see Figure 5 (a)). Now we can join two of such cycles C' and C
ℜ 
with cycle C’” 
with edge set ((E(C') U E(CR)) \ {(x, 2i)(x, 2i + 1), (y
3
, 2i)(y
3
, 2i + 1)}) U {(x,2i)(y
3
,2i),(x,2i+1)(y
3
,2i+1)} 
(see Figure 5 (b)).
Figure 5: The redesigned standard Hamiltonian cycle CR for P3□Pn (a) and joining standard 
cycles C’ = P3□Pn and CR (b)
For t = 2, 3,.. we repeat the following until we reach a Hamiltonian cycle for T□Pn. Let C
t
 be a 
component of T \ C
t-1
 such that there is a vertex x ϵ C
t
 incident with the vertex on C
t-1
. We join 
standard Hamiltonian cycle C
t
□Pn with the cycle C
t-1
□Pn as described above. The construction is 
correct since it consists of the repeated joining of cycles at incident vertices in T, and there are 
enough free edges to join all standard Hamiltonian cycles, namely:
• for every x ϵ C
t-1
 of type EP2, we have at most deg
T
 (x)–1 ≤ n/2–1 = (n-2)/2 component C
j
 ad-
jacent with x, so there are enough free vertical edges on P
n
-layer P
nx
 to join cycle C’ = C
t-1
□P
n
 
with all cycles C” = C
j
□P
n
 as described above;
• for every x ϵ C
t-1
 of type M, we have at most deg
T
(x)–2 ≤ (n+2)/2–2 = (n-2)/2 component C
j 
adjacent with x, so there are enough free vertical edges on P
n
-layer P
nx 
to join cycle C’ = C
t-1
□P
n
 
with all cycles C” = C
j
□P
n
 as described above;
• for every x,y ϵ C
t-1 
of type EPL and EPR, we have at most deg
T
(x)+deg
T
(
y
)–2 ≤ (n+2)/2–2 = (n-2)/2 
component C
j
 adjacent with x and y, so there are enough free vertical edges on P
n
-layer P
nx
 or 
P
ny
 to join cycle C’ = C
t-1
□P
n
 with all cycles C” = C
j
□P
n
 as described above.
□
References
[1] V. Batagelj, T. Pisanski: Hamiltonian cycle in the cartesian product of a tree and a cycle, 
Discrete Math. 38, 311 – 312, 1982
[2] R. Čada, E. Flandrin, H. Li: Hamiltonicity and pancyclicity of cartesian products of 
graphs, Discrete Math. 309, 6337 – 6343, 1987
[3] V. Dimakopoulos, L. Palios, A. S. Poulakidas: On the Hamiltonicity of the Cartesian 
product, Inform. Process. Lett. 96, 49 – 53, 2005
[4] L. Kao, C. Weng: The Relation Between Hamiltonian and 1-Tough Properties of the Car-
tesian Product Graphs, Graphs Comb., 2020
[5] M. Rosenfeld, D. Barnette: Hamiltonian circuits in certain prisms, Discrete Math. 5, 
389394, 1973