Electronic Journal of Graph Theory and Applications 13 (1) (2025), 141–161

Hamiltonicity in directed Toeplitz
graphs Tn⟨1, 3, 6; t⟩
Shabnam Malik
Faculty of Mathematics, Forman Christian College (A Chartered University) Lahore, Pakistan.
shabnam.malik@gmail.com

Abstract
A directed Toeplitz graph, denoted as Tn ⟨s1 , . . . , sk ; t1 , . . . , tl ⟩ of order n, is a digraph in which an
edge (i, j) exists if and only if j − i = sp or i − j = tq for some 1 ≤ p ≤ k and 1 ≤ q ≤ l.
The adjacency matrix of such a graph forms a Toeplitz matrix, characterized by constant values
along all diagonals parallel to the main diagonal. In this paper, we explore the Hamiltonicity of
directed Toeplitz graphs of the form Tn ⟨1, 3, 6; t⟩. We establish that Tn ⟨1, 3, 6; t⟩ is Hamiltonian for
t = 5, 10 and for all t ≥ 12, for every n. Additionally, we show that the graph remains Hamiltonian
for all n, with only a finite number of exceptions when t = 3, 4, 6, 7, 8, 9 and 11. Specifically, for
t = 1, the graph is Hamiltonian only when n = 7, while for t = 2, it is Hamiltonian under certain
conditions on n, namely when n ≡ 0, 1, 3 (mod 4).
Keywords: adjacency matrix, Toeplitz graph, Hamiltonian graph
Mathematics Subject Classification : 05C45
DOI: 10.5614/ejgta.2025.13.1.10

1. Introduction
For a graph G, let V (G) and E(G) denote its vertex set and edge set, respectively. An edge
(u, v) is called an increasing edge if u < v and a decreasing edge if u > v. The length of
an edge (u, v) is defined as |u − v|. A path is a sequence of edges that connects a sequence of
distinct vertices. A closed path is called a cycle. A Hamiltonian path is a path that visits each
Received: 7 August 2024,

Revised: 25 March 2025,

141

Accepted: 2 April 2025.

www.ejgta.org

Hamiltonicity in directed Toeplitz graphs Tn ⟨1, 3, 6; t⟩

|

Shabnam Malik

vertex of the graph exactly once. A graph that contains a Hamiltonian path is called traceable.
Similarly, a Hamiltonian cycle is a cycle that visits each vertex exactly once, and a graph containing
a Hamiltonian cycle is called Hamiltonian. A graph S is a subgraph of G if V (S) ⊂ V (G) and
E(S) ⊂ E(G). If V (S) = V (G), then S is said to span G. Consequently, if S is a spanning cycle
of G, then S is Hamiltonian.
A Toeplitz matrix, named after Otto Toeplitz (1881-1940), is a square matrix in which each
diagonal parallel to the main diagonal has constant values. That is, a Toeplitz matrix has the form:


a0
a1
a2
· · · an−1
 a−1
a0
a1
· · · an−2 


 a−2
a−1
a0
· · · an−3 


 ..
..
..
.. 
.
.
 .
.
.
.
. 
a−(n−1) a−(n−2) a−(n−3) · · · a0
A Toeplitz matrix is called a circulant matrix if ai = ai−n for i = 1, . . . , n − 1. Toeplitz matrices
appear in various fields of applied mathematics and engineering, including queuing theory, signal
processing, time series analysis, and integral equations. Circulant matrices, a notable subclass
of Toeplitz matrices, also have significant applications in areas such as signal processing, errorcorrecting codes, image processing, cryptography, and numerical analysis.
A directed or undirected graph whose adjacency matrix is Toeplitz is called a Toeplitz graph,
while one whose adjacency matrix is circulant is called a circulant graph.
For a Toeplitz matrix of order n, the main diagonal is labeled as 0, and the n − 1 distinct
diagonals above and below it are labeled 1, 2, . . . , n − 1. Let s1 , s2 , . . . , sk and t1 , t2 , . . . , tl represent the upper and lower diagonals, respectively, that contain ones, where 0 < s1 < s2 <
· · · < sk < n, 0 < t1 < t2 < · · · < tl < n. The corresponding Toeplitz graph is denoted
by Tn ⟨s1 , s2 , . . . , sk ; t1 , t2 , . . . , tl ⟩, where n > max{sk , tl }. This graph consists of the vertex set
{1, 2, . . . , n}, , with an edge (i, j) if and only if j −i = sp or i−j = tq for some p and q satisfying
1 ≤ p ≤ k and 1 ≤ q ≤ l. Clearly, every increasing edge has length sp for some p, and every decreasing edge has length tq for some q. Additionally, note that the graphs Tn ⟨s1 , . . . , si ; t1 , . . . , tj ⟩
and Tn ⟨t1 , . . . , tj ; s1 , . . . , si ⟩ are obtained from each other by reversing the orientation of all edges.
Circulant graphs and their various properties have been extensively studied by several authors
(see [8]-[11], [20]-[21], [23], [39]-[41], and [43], among others). In particular, Boesch and Tindell
[8] conjectured that all undirected connected circulant graphs are Hamiltonian, a result later proved
by Burkard and Sandholzer [10].
Various properties of Toeplitz graphs, including colorability, planarity, bipartiteness, connectivity, cycle discrepancy, edge irregularity strength, decomposition, labeling, and metric dimension,
have been explored in [2]-[7], [13]-[17], [19], [22], [37], and [38]. The Hamiltonian properties
of Toeplitz graphs were first investigated by R. van Dal et al. [12] and subsequently studied in
[18, 36, 42]. The study of Hamiltonicity in directed Toeplitz graphs was initiated by S. Malik and
T. Zamfirescu [35] and further examined by S. Malik [24], S. Malik and A.M. Qureshi [32, 33], as
well as S. Malik in [25]-[31], and S. Malik and F. Ramezani in [34].
The Hamiltonicity of the Toeplitz graphs Tn ⟨1, 3, 4; t⟩ was studied in [29, 30], while [33] examined the Hamiltonicity of Tn ⟨1, 3, 5; t⟩. In this paper, we maintain s1 = 1 and s2 = 3 but consider
142

www.ejgta.org

Hamiltonicity in directed Toeplitz graphs Tn ⟨1, 3, 6; t⟩

|

Shabnam Malik

s3 = 6, focusing on the Hamiltonicity of Tn ⟨1, 3, 6; t⟩. Throughout, we consider finite directed
graphs without multiple edges or loops.
Hamiltonicity results for undirected Toeplitz graphs directly influence the directed case. In particular, if Tn ⟨t1 , t2 , . . . , ti ⟩ is Hamiltonian, then the corresponding directed Toeplitz graph Tn ⟨t1 , . . . ,
ti ; t1 , . . . , ti ⟩ is also Hamiltonian.
For a vertex a in Tn ⟨1, 3, 6; t⟩, we define paths Pa→a+4 and Qa→a+4 as follow:
Pa→a+4 = (a, a + 3, a + 4)
Qa→a+4 = (a, a − 2, a + 4)
These paths are illustrated in Figure 1.
Pa

a+4

:

Qa

a+4

a+3 a+4

a

:

a

a-2

a+2

a+4

Figure 1. Paths Pa→a+4 and Qa→a+4 in Tn ⟨1, 3, 6; t⟩.

Remark 1.1. If the Toeplitz graph Tn ⟨1, 3, 6; t⟩ has a Hamiltonian cycle containing the edge (n-2,
n-1), then the extended graph Tn+(t−1) ⟨1, 3, 6; t⟩ also possesses this property. This follows because
a Hamiltonian cycle in Tn ⟨1, 3, 6; t⟩ can be modified into a Hamiltonian cycle in Tn+(t−1) ⟨1, 3, 6; t⟩
by replacing the edge (n-2, n-1) with the path (n-2, n+1, n+2,. . . , n+(t-1), n-1), thereby preserving the Hamiltonian property. For instance, as illustrated in Figure 2, a Hamiltonian cycle in
T10 ⟨1, 3, 6; 5⟩ is transformed into a Hamiltonian cycle in T14 ⟨1, 3, 6; 5⟩ by replacing the edge (8, 9)
with the path (8, 11, 12, 13, 14, 9). This process can be repeated to extend the Hamiltonian cycle
to T18 ⟨1, 3, 6; 5⟩, and so forth.

1

1

2

3

2

4

3

4

5

6

5

6

7

8

8

7

9

9

10

10 11 12 13 14

Figure 2. Hamiltonian cycles in T10 ⟨1, 3, 6; 5⟩ and T14 ⟨1, 3, 6; 5⟩.

143

www.ejgta.org

Hamiltonicity in directed Toeplitz graphs Tn ⟨1, 3, 6; t⟩

|

Shabnam Malik

2. Toeplitz Graphs Tn ⟨1, 3, 6; t ≤ 8⟩
For t = 1, it is clear that Tn ⟨1, 3, 6; 1⟩ is Hamiltonian if and only if n = 7. This is because
the only decreasing edges-edges of the form (a, b) where a > b-have length one, which is only
possible when n = 7. Moreover, it is easily verified that T7 ⟨1, 3, 6; 1⟩ has a unique Hamiltonian
cycle given by (1, 7, 6, 5, 4, 3, 2, 1).
Theorem 2.1. The Toeplitz graph Tn ⟨1, 3, 6; 2⟩ is Hamiltonian if and only if n ≡ 0, 1, 3 (mod 4).
Proof. If n ≡ 0 (mod 4), then a Hamiltonian cycle in Tn ⟨1, 3, 6; 2⟩ is given by (1, 4) ∪ Q4→8 ∪
Q8→12 ∪· · ·∪Qn−4→n ∪(n, n−2, n−1, n−3, n−5, . . . , 1), as illustrated in Figure 3. If n ≡ 1 mod 4,

2

1

4

3

5

7

6

8

9 10

11 12 13 14 15

16

Figure 3. Hamiltonian cycles in T16 ⟨1, 3, 6; 2⟩.

then a Hamiltonian cycle in Tn ⟨1, 3, 6; 2⟩ is (1, 4) ∪ Q4→8 ∪ Q8→12 ∪ · · · ∪ Qn−5→n−1 ∪ (n − 1, n −
3, n, n − 2, n − 4, . . . , 1), as shown in Figure 2. If n ≡ 3 mod 4, then a Hamiltonian cycle in

1

2

4

3

7

6

5

8

9 10

11 12 13 14

15

16 17

Figure 4. Hamiltonian cycles in T17 ⟨1, 3, 6; 2⟩.

Tn ⟨1, 3, 6; 2⟩ is (1, 7) ∪ Q7→11 ∪ Q11→15 ∪ · · · ∪ Qn−4→n ∪ (n, n − 2, n − 1, n − 3, n − 5, . . . , 2, 3, 1),
as shown in Figure 5. Thus, Tn ⟨1, 3, 6; 2⟩ is Hamiltonian for n ≡ 0, 1, 3 mod 4.

1

2

3

4

5

6

7

8

9 10

11

12 13

14

15 16 17 18 19

Figure 5. Hamiltonian cycles in T19 ⟨1, 3, 6; 2⟩.

Note that the Hamiltonicity of Tn ⟨1, 3, 6; 2⟩ for n ∼
= 2 mod 4 remains undetermined.
Theorem 2.2. Tn ⟨1, 3, 6; 3⟩ is Hamiltonian for all n except for n = 7, 8, 9, 12, 14, 16.
Proof. To prove this theorem, we will demonstrate that Tn ⟨1, 3, 6; 3⟩ is Hamiltonian for all odd
n ≥ 11, and for all even n ≥ 18, and for n = 10. A Hamiltonian cycle in T11 ⟨1, 3, 6; 3⟩ is (1, 2, 3,
9, 10, 11, 8, 5, 6, 7, 4, 1). A Hamiltonian cycle in T18 ⟨1, 3, 6; 3⟩ is (1, 2, 3, 9, 10, 16, 17, 18, 15,
12, 13, 14, 11, 8, 5, 6, 7, 4, 1). These Hamiltonian cycles contain the edge (n-2, n-1), which allows
them to be extended to Hamiltonian cycles in Tn+2 ⟨1, 3, 6; 3⟩ by replacing the edge (n-2, n-1) with
144

www.ejgta.org

Hamiltonicity in directed Toeplitz graphs Tn ⟨1, 3, 6; t⟩

|

Shabnam Malik

the path (n-2, n+1, n+2, n-1). This transformation preserves the Hamiltonicity property, proving
that Tn ⟨1, 3, 6; 3⟩ is Hamiltonian for all even n ≥ 18 and all odd n ≥ 11. For n = 10, the unique
Hamiltonian cycle in T10 ⟨1, 3, 6; 3⟩ is (1, 2, 8, 5, 6, 3, 9, 10, 7, 4, 1). This completes the proof.
Note that the Hamiltonicity of Tn ⟨1, 3, 6; 3⟩ for n = 7, 8, 9, 12, 14 and 16 remains undetermined.
Theorem 2.3. Tn ⟨1, 3, 6; 4⟩ is Hamiltonian for all n except for n = 12.
Proof. We prove it by considering cases based on n mod 3.
Case 1. Let n ≡ 0 mod 3 and n ̸= 12.
The smallest such n is 9. A Hamiltonian cycle in T9 ⟨1, 3, 6; 4⟩ is (1, 2, 8, 4, 7, 3, 6, 9, 5, 1),
which does not include the edge (7, 8). The next representative in this class, different from 12, is
15. A Hamiltonian cycle in T15 ⟨1, 3, 6; 4⟩ is (1, 2, 8, 9, 10, 6, 12, 13, 14, 15, 11, 7, 3, 4, 5, 1).
Case 2. Let n ≡ 1 mod 3.
The smallest such n is 7. A Hamiltonian cycle in T7 ⟨1, 3, 6; 4⟩ is (1, 4, 7, 3, 6, 2, 5, 1).
This cycle does not contain the edge (5, 6). The next representative in this class is n = 10. A
Hamiltonian cycle in T10 ⟨1, 3, 6; 4⟩ is (1, 2, 8, 9, 10, 6, 7, 3, 4, 5, 1).
Case 3. Let n ≡ 2 mod 3.
The smallest such n is 8. A Hamiltonian cycle in T8 ⟨1, 3, 6; 4⟩ is (1, 2, 3, 6, 7, 8, 4, 5, 1).
For n = 8, 10, 15, these Hamiltonian cycles contain the edge (n-2, n-1). By Remark 1.1, we can
extend these Hamiltonian cycles to Tn+3 ⟨1, 3, 6; 4⟩ by replacing the edge (n-2, n-1) with the path
(n-2, n+1, n+2, n+3, n-1), which preserves the same property. Suppose, for some non-negative
integer r, if Tn=no +3r̸=12 ⟨1, 3, 6; 4⟩ has a Hamiltonian cycle containing the edge (n-2, n-1), then
Tn+3 ⟨1, 3, 6; 4⟩ also has the same property. Thus we conclude that Tn ⟨1, 3, 6; 4⟩ is Hamiltonian for
all n ̸= 12.
Note that the Hamiltonicity of T12 ⟨1, 3, 6; 4⟩ remains undetermined.
Theorem 2.4. Tn ⟨1, 3, 6; 5⟩ is Hamiltonian for all n.
Proof. We prove it by considering cases based on n mod 4.
Case 1. Let n ≡ 0 mod 4.
The smallest n in this case is 8. A Hamiltonian cycle in T8 ⟨1, 3, 6; 5⟩ is (1, 7, 2, 8, 3, 4, 5,
6, 1), which does not contain the edge (6, 7). The next representative in this class is 12, where a
Hamiltonian cycle in T12 ⟨1, 3, 6; 5⟩ is (1, 4, 5, 8, 9, 10, 11, 12, 7, 2, 3, 6, 1).
Case 2. Let n ≡ 1 mod 4.
The first two representatives in this class are n = 9 and 13, but for both, the Hamiltonian cycles
do not contain the edge (n − 2, n − 1). A Hamiltonian cycle in T9 ⟨1, 3, 6; 5⟩ is (1, 7, 2, 8, 3, 9, 4,
5, 6, 1). A Hamiltonian cycle in T13 ⟨1, 3, 6; 5⟩ is (1, 4, 10, 13, 8, 3, 9, 12, 7, 2, 5, 11, 6, 1). Now, the
next representative in this class is n = 17. A Hamiltonian cycle in T17 ⟨1, 3, 6; 5⟩ is (1, 4, 5, 8, 9,
10, 13, 14, 15, 16, 11, 17, 12, 7, 2, 3, 6, 1).
Case 3. Let n ≡ 2 mod 4.

145

www.ejgta.org

Hamiltonicity in directed Toeplitz graphs Tn ⟨1, 3, 6; t⟩

|

Shabnam Malik

The smallest n in this case is 10. A Hamiltonian cycle in T10 ⟨1, 3, 6; 5⟩ is (1, 2, 3, 4, 7, 8, 9, 10,
5, 6, 1).
Case 4. Let n ≡ 3 mod 4.
The smallest n in this case is 7. A Hamiltonian cycle in T7 ⟨1, 3, 6; 5⟩ is (1, 7, 2, 3, 4, 5, 6, 1).
For n = 7, 10, 12, 17, these Hamiltonian cycles contain the edge (n-2, n-1). Thus, these cycles
in Tn∈{7,10,12,17} ⟨1, 3, 6; 5⟩ can be transformed into Hamiltonian cycles in Tn+4 ⟨1, 3, 6; 5⟩ by replacing the edge (n-2, n-1) with the path (n-2, n+1, n+2, n+3, n+4, n-1), which preserves the same
property. Using the technique described in Remark 1.1, it follows that Tn ⟨1, 3, 6; 5⟩ is Hamiltonian
for all n.
Theorem 2.5. Tn ⟨1, 3, 6; 6⟩ is Hamiltonian for all n except n = 10 and n = 14.
Proof. We prove it by considering cases based on n mod 5.
Case 1. Let n ≡ 0 mod 5 and n ̸= 10.
The smallest such n after 10 is n = 15. A Hamiltonian cycle in T15 ⟨1, 3, 6; 6⟩ is (1, 4, 5, 11,
12, 15, 9, 10, 13, 14, 8, 2, 3, 6, 7, 1), which contains the edge (13, 14).
Case 2. Let n ≡ 1 mod 5.
The smallest such n is n = 11. A Hamiltonian cycle in T11 ⟨1, 3, 6; 6⟩ is (1, 2, 8, 9, 3, 4, 10, 11,
5, 6, 7, 1), which does not contain the edge (9, 10). The next representative in this class is n = 16.
A Hamiltonian cycle in T16 ⟨1, 3, 6; 6⟩ is (1, 2, 5, 8, 11, 14, 15, 9, 3, 6, 12, 13, 16, 10, 4, 7, 1), which
contains the edge (14, 15).
Case 3. Let n ≡ 2 mod 5.
The smallest such n is n = 7. A Hamiltonian cycle in T7 ⟨1, 3, 6; 6⟩ is (1, 2, 3, 4, 5, 6, 7, 1),
which contains the edge (5, 6)
Case 4. Let n ≡ 3 mod 5.
The smallest such n is n = 8. A Hamiltonian cycle in T8 ⟨1, 3, 6; 6⟩ is (1, 4, 5, 8, 2, 3, 6, 7, 1),
which contains the edge (6, 7).
Case 5. Let n ≡ 4 mod 5 and n ̸= 14.
The smallest such n is n = 9. A Hamiltonian cycle in T9 ⟨1, 3, 6; 6⟩ is (1, 2, 8, 9, 3, 4, 5, 6, 7,
1), which does not contain the edge (7, 8). The next representative in this class after 14 is n = 19.
A Hamiltonian cycle in T19 ⟨1, 3, 6; 6⟩ is (1, 2, 3, 4, 10, 11, 5, 8, 14, 17, 18, 12, 6, 9, 15, 16, 19, 13,
7, 1), which contains the edge (17, 18).
For n = 7, 8, 15, 16, 19, the Hamiltonian cycles above contain the edge (n-2, n-1). This allows
us to extend the cycles to Tn+5 ⟨1, 3, 6; 6⟩ by replacing the edge (n-2, n-1) with the path (n − 2, n +
1, n + 2, n + 3, n + 4, n − 1), which preserves the same property. By applying the technique in
Remark 1.1, it follows that Tn ⟨1, 3, 6; 6⟩ is Hamiltonian for all n except n = 10 and n = 14.
Note that for n ∈ {10, 14}, the Hamiltonicity of Tn ⟨1, 3, 6; 6⟩ remains undecided.
Theorem 2.6. Tn ⟨1, 3, 6; 7⟩ is Hamiltonian for all n except n = 9 and n = 12.
Proof. We prove it by considering cases based on n mod 6.
Case 1. Let n ≡ 0, 1, 2, 3, 5 mod 6 and n ∈
/ {9, 12}.
The smallest such values of n ∈
/ {9, 12} are n = 18, 13, 8, 15, 11, respectively. Hamiltonian cycles
for these values are:
146

www.ejgta.org

Hamiltonicity in directed Toeplitz graphs Tn ⟨1, 3, 6; t⟩

|

Shabnam Malik

n = 18 : (1, 4, 5, 6, 12, 15, 18, 11, 14, 7, 13, 16, 17, 10, 3, 9, 2, 8,1),
n = 13 : (1, 2, 3, 4, 7, 13, 6, 9, 10, 11, 12, 5, 8, 1),
n = 8 : (1, 2, 3, 4, 5, 6, 7, 8, 1),
n = 15 : (1, 2, 3, 6, 9, 12, 5, 11, 4, 7, 10, 13, 14, 15, 8, 1),
n = 11 : (1, 2, 3, 9, 10, 11, 4, 5, 6, 7, 8, 1).
Each of these cycles contains the edge (n-2,n-1). Thus, these cycles can be extended to Tn+6 ⟨1, 3, 6; 7⟩
by replacing the edge (n-2, n-1) with the path (n-2, n+1, n+2, n+3, n+4, n-1), which preserves the
same property.
Case 2. Let n ≡ 4 mod 6.
The smallest such n is n = 10. A Hamiltonian cycle in T10 ⟨1, 3, 6; 7⟩ is (1, 2, 5, 6, 9, 10, 3, 4,
7, 8, 1), which does not contain the edge (8, 9). The next representative in this class is n = 16. A
Hamiltonian cycle in T16 ⟨1, 3, 6; 7⟩ is (1, 4, 7, 10, 13, 16, 9, 2, 3, 6, 12, 5, 11, 14, 15, 8, 1), which
contains the edge (14, 15). Thus, this cycle can also be extended to Tn+6 ⟨1, 3, 6; 7⟩ using the same
extension technique.
By applying the technique in Remark 1.1, it follows that Tn ⟨1, 3, 6; 7⟩ is Hamiltonian for all n
except n = 9 and n = 12.
Note that for n ∈ {9, 12}, the Hamiltonicity of Tn ⟨1, 3, 6; 7⟩ has not yet been determined.
Theorem 2.7. Tn ⟨1, 3, 6; 8⟩ is Hamiltonian for all n ̸= 10.
Proof. We prove it by considering cases based on n mod 7.
Case 1. n ≡ 0, 1, 2, 3, 5, 6 mod 7 and n ̸= 10.
The smallest such values of n ̸= 10 are n = 14, 15, 9, 17, 12, 13, respectively. Hamiltonian cycles
for these values are:
n = 14 : (1, 4, 5, 8, 11, 12, 13, 14, 6, 7, 10, 2, 3, 9, 1),
n = 15 : (1, 4, 5, 8, 11, 12, 13, 14, 15, 7, 10, 2, 3, 6, 9, 1),
n = 9 : (1, 2, 3, 4, 5, 6, 7, 8, 9, 1),
n = 17 : (1, 2, 5, 6, 12, 15, 16, 8, 11, 3, 4, 7, 10, 13, 14, 17, 9, 1),
n = 12 : (1, 2, 3, 6, 7, 10, 11, 12, 4, 5, 8, 9, 1),
n = 13 : (1, 2, 3, 4, 10, 11, 12, 13, 5, 6, 7, 8, 9, 1).
Each of these cycles contains the edge (n-2, n-1). Thus, these cycles can be extended to
Tn+7 ⟨1, 3, 6; 8⟩ by replacing the edge (n − 2, n − 1) with the path (n − 2, n + 1, n + 2, n +
3, n + 4, n − 1), which preserves the same property.
Case 2. n ≡ 4 mod 7.
The smallest such n is n = 11. A Hamiltonian cycle in T11 ⟨1, 3, 6; 8⟩ is (1, 7, 8, 11, 3, 4, 10, 2, 5,
6, 9, 1), which does not contain the edge (9, 10). The next representative in this class is n = 18.
A Hamiltonian cycle in T18 ⟨1, 3, 6; 8⟩ is (1, 4, 5, 11, 12, 13, 14, 15, 16, 17, 18, 10, 2, 3, 6, 7, 8, 9,
1), which contains the edge (16, 17). Thus, this cycle can also be extended to Tn+7 ⟨1, 3, 6; 8⟩ using
the same extension technique.
By applying the technique in Remark 1.1, it follows that Tn ⟨1, 3, 6; 8⟩ is Hamiltonian for all
n ̸= 10.
Note that the Hamiltonicity of T10 ⟨1, 3, 6; 8⟩ has not yet been determined.
147

www.ejgta.org

Hamiltonicity in directed Toeplitz graphs Tn ⟨1, 3, 6; t⟩

|

Shabnam Malik

3. Toeplitz Graphs Tn ⟨1, 3, 6; t ≥ 9⟩
Theorem 3.1. Let t ∈ {9, 11}. For all n ̸= 13, the graph Tn ⟨1, 3, 6; t⟩ is Hamiltonian.
Proof. Case 1. t = 9
We analyze values of n mod 8.
(i) If n ≡ 0, 1, 2, 3, 5, 6, 7 mod 8 and n ̸= 13.
The smallest such values of n ̸= 13 are n = 16, 17, 10, 11, 21, 14, 15, respectively. Hamiltonian
cycles for these values are:
n = 16 : (1, 5, 6, 12, 13, 14, 15, 16, 7, 8, 11, 2, 3, 9, 10, 1),
n = 17 : (1, 4, 7, 13, 14, 15, 16, 17, 8, 11, 2, 5, 6, 12, 3, 9, 10, 1),
n = 10 : (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 1),
n = 11 : (1, 4, 5, 11, 2, 3, 6, 7, 8, 9, 10, 1),
n = 21 : (1, 7, 8, 14, 15, 16, 17, 18, 19, 20, 21, 12, 13, 4, 5, 11, 2, 3, 6, 9, 10, 1),
n = 14 : (1, 2, 3, 4, 7, 8, 11, 12, 13, 14, 5, 6, 9, 10, 1),
n = 15 : (1, 2, 3, 4, 5, 11, 12, 13, 14, 15, 6, 7, 8, 9, 10, 1). Each of these cycles contains the edge
(n-2, n-1). Thus, these cycles can be extended to Tn+8 ⟨1, 3, 6; 9⟩ by replacing the edge (n-2, n-1)
with the path (n-2, n+1, n+2, n+3, n+4, n-1), which preserves the same property.
(ii) If n ≡ 4 mod 8.
The smallest such n is n = 12. A Hamiltonian cycle in T12 ⟨1, 3, 6; 9⟩ is (1, 7, 8, 11, 2, 5, 6, 9,
12, 3, 4, 10, 1), which does not contain the edge (10, 11). The next representative in this class is
n = 20. A Hamiltonian cycle in T20 ⟨1, 3, 6; 9⟩ is (1, 4, 5, 8, 9, 12, 13, 14, 15, 16, 17, 18, 19, 20,
11, 2, 3, 6, 7, 10, 1), which contains the edge (18, 19). Thus, this cycle can also be extended to
Tn+8 ⟨1, 3, 6; 9⟩ using the same extension technique.
Case 2. t = 11
We analyze values of n mod 10.
(i) If n ≡ 0, 1, 2, 3, 5, 7, 8, 9 mod 10 and n ̸= 13.
The smallest such values of n ̸= 13 are n = 20, 21, 12, 23, 15, 17, 18, 19, respectively. Hamiltonian
cycles for these values are:
n = 20 : (1, 2, 3, 4, 5, 6, 7, 10, 13, 14, 20, 9, 15, 16, 17, 18, 19, 8, 11, 12, 1),
n = 21 : (1, 4, 5, 6, 7, 8, 14, 15, 16, 17, 18, 19, 20, 21, 10, 13, 2, 3, 9, 12, 1),
n = 10 : (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 1),
n = 23 : (1, 2, 8, 9, 15, 21, 22, 11, 14, 3, 4, 5, 6, 7, 10, 13, 16, 17, 18, 19, 20, 23, 12, 1),
n = 15 : (1, 2, 3, 13, 14, 15, 4, 5, 8, 9, 10, 11, 12, 1),
n = 17 : (1, 2, 3, 4, 10, 13, 14, 15, 16, 5, 11, 17, 6, 7, 8, 9, 12, 1),
n = 18 : (1, 2, 3, 4, 5, 6, 9, 10, 13, 14, 15, 16, 17, 18, 7, 8, 11, 12, 1),
n = 19 : (1, 2, 3, 4, 5, 6, 7, 13, 14, 15, 16, 17, 18, 19, 8, 9, 10, 11, 12, 1).
Each of these cycles contains the edge (n-2,n-1), allowing extension to Tn+10 ⟨1, 3, 6; 11⟩ using the
same method.
(ii) If n ≡ 4, 6 mod 10.
The smallest such values are n = 14 and n = 16, with Hamiltonian cycle (1, 2, 5, 6, 9, 10, 13, 14,
3, 4, 7, 8, 11, 12, 1) and (1, 2, 8, 9, 15, 16, 5, 6, 7, 13, 14, 3, 4, 10, 11, 12, 1), respectively. These
cycles do not contain the edge (n-2, n-1). The next representative in these classes are n = 24 and
n = 16, with Hamiltonian cycles (1, 7, 8, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 13, 2, 3, 4, 5,
148

www.ejgta.org

Hamiltonicity in directed Toeplitz graphs Tn ⟨1, 3, 6; t⟩

|

Shabnam Malik

6, 9, 10, 11, 12, 1) and (1, 2, 8, 9, 10, 11, 17, 18, 24, 25, 14, 3, 4, 5, 6, 7, 13, 16, 19, 20, 26, 15,
21, 22, 23, 12, 1), respectively, containing the edge (n-2, n-1), and thus allow extension using the
same technique.
By applying the extension technique in Remark 1.1, we conclude that for t ∈ {9, 11}, the graph
Tn ⟨1, 3, 6; t⟩ is Hamiltonian for all n ̸= 13.
Note that for n = 13, the Hamiltonicity of Tn ⟨1, 3, 6; 9⟩ and Tn ⟨1, 3, 6; 11⟩ has not yet been
determined.
Now we prove that for t = 10 or t ≥ 12, the graph Tn ⟨1, 3, 6; t⟩ is Hamiltonian for all n.
Theorem 3.2. Let t = 10 or t ≥ 12. Then Tn ⟨1, 3, 6; t⟩ is Hamiltonian for all n.
Proof. Let t = 10 or t ≥ 12. We prove it by considering cases based on n mod t − 1.
Case 1. n ≡ 0 mod (t − 1).
The smallest value of n distinct from t − 1, is n = 2t − 2. We analyze values of t mod 4.
(i) If t ≡ 0 mod 4, we construct a Hamiltonian cycle in the graph Tn=2t−2 ⟨1, 3, 6; t⟩ as P1→5 ∪
P5→9 ∪ · · · ∪ Pt−7→t−3 ∪ (t − 3, t, t + 3, t + 4, . . . , n − 2, n − 1, n, n − t = t − 2, t − 1, t + 2, 2, 3) ∪
P3→7 ∪ P7→11 ∪ · · · ∪ Pt−9→t−5 ∪ (t − 5, t + 1, 1). See Figure 6 for an illustration of the cycle.
(ii) If t ≡ 1 mod 4, a Hamiltonian cycle in Tn=2t−2 ⟨1, 3, 6; t⟩ is given by P1→5 ∪ P5→9 ∪ · · · ∪
Pt−8→t−4 ∪ (t − 4, t + 2, 2, 3) ∪ P3→7 ∪ P7→11 ∪ · · · ∪ Pt−10→t−6 ∪ (t − 6, t − 3, t + 3, t + 4, . . . , n −
2, n − 1, n, n − t = t − 2, t − 1, t, t + 1, 1). See Figure 7 for an illustration.
(iii) If t ≡ 2 mod 4, a Hamiltonian cycle in Tn=2t−2 ⟨1, 3, 6; t⟩ is given by (1, 2, 3) ∪ P3→7 ∪
P7→11 ∪ · · · ∪ Pt−11→t−7 ∪ (t − 7, t − 1, t + 5) ∪ Pt+5→t+10 ∪ Pt+10→t+14 ∪ · · · ∪ Pn−7→n−3 ∪ (n −
3, n, n − t = t − 2, t + 4, 4, 5) ∪ P5→9 ∪ P9→13 ∪ · · · ∪ Pt−9→t−5 ∪ (t − 5, t − 4, t + 2, t + 3) ∪
Pt+3→t+7 ∪ Pt+7→t+11 ∪ · · · ∪ Pn−5→n−1 ∪ (n − 1, n − 1 − t = t − 3, t, t + 1, 1). See Figure 8 for
an illustration.
(iv) If t ≡ 3 mod 4, a Hamiltonian cycle in the graph Tn=2t−2 ⟨1, 3, 6; t⟩ is given by P1→5 ∪
P5→9 ∪ · · · ∪ Pt−14→t−10 ∪ (t − 10, t − 4, t − 3, t, t + 3, t + 4, . . . , n − 2, n − 1, n, n − t =
t − 2, t − 1, t + 2, 2, 3) ∪ P3→7 ∪ P7→11 ∪ · · · ∪ Pt−12→t−8 ∪ (t − 8, t − 7, t − 6, t − 5, t + 1, 1).
See Figure 9 for an illustration.
These Hamiltonian cycles in each class contain the edge (n-2, n-1). Suppose that for some
non-negative integer r, the graph Tn=(2t−2)+r(t−1) ⟨1, 3, 6; t⟩ has a Hamiltonian cycle containing the
edge (n-2, n-1). Then, by Remark 1.1, the graph Tn+t−1 ⟨1, 3, 6; t⟩ also has a Hamiltonian cycle
with the same property. Thus, Tn ⟨1, 3, 6; t⟩ is Hamiltonian for all n ≡ 0 mod (t − 1).
Case 2. n ≡ 1 mod (t − 1).
The smallest n, distinct from t, is n = 2t − 1. We analyze values of t mod 4.
(i) If t ≡ 0 mod 4, a Hamiltonian cycle in the graph Tn=2t−1 ⟨1, 3, 6; t⟩ is given by P1→5 ∪
P5→9 ∪ · · · ∪ Pt−7→t−3 ∪ (t − 3, t, t + 3, t + 4, . . . , n − 2, n − 1, n, n − t = t − 1, t + 2, 2, 3) ∪
P3→7 ∪ P7→11 ∪ · · · ∪ Pt−9→t−5 ∪ (t − 5, t − 2, t + 1, 1). See Figure 10 for an illustration.
(ii) If t ≡ 1 mod 4, a Hamiltonian cycle in the graph Tn=2t−1 ⟨1, 3, 6; t⟩ is given by (1, 2) ∪
P2→6 ∪ P6→10 ∪ · · · ∪ Pt−15→t−11 ∪ (t − 11, t − 5, t − 4, t + 2, t + 3, 3, 4) ∪ P4→8 ∪ P8→12 ∪ · · · ∪
Pt−13→t−9 ∪ (t−9, t−8, t−7, t−6, t−3, t−2, t+4, t+5, . . . , n−2, n−1, n, n−t = t−1, t, t+1, 1).
See Figure 11 for an illustration.
149

www.ejgta.org

Hamiltonicity in directed Toeplitz graphs Tn ⟨1, 3, 6; t⟩

|

Shabnam Malik

...
2

1

3

4

6

5

9

8

7

10 11

12 13

14 15

16 17

29 30

18 19 20 21

Figure 6. A Hamiltonian cycle in T30 ⟨1, 3, 6; 16⟩ .

...
2

1

3

4

6

5

9

8

7

10 11

12 13

14 15

30 32

19 20 21

16 17 18

Figure 7. A Hamiltonian cycle in T32 ⟨1, 3, 6; 17⟩ .

21
2

1

3

4

5

6

7

8

9 10 11 12 13 14 15

16 17

18 19

20

22 23 24

25 26

Figure 8. A Hamiltonian cycle in T26 ⟨1, 3, 6; 14⟩ .

...
1

2

3 4

5

6

7

8

9

10 11 121314 15 16

17 18

19 20

21 22 23

35 36

Figure 9. A Hamiltonian cycle in T36 ⟨1, 3, 6; 19⟩.

(iii) If t ≡ 2 mod 4, a Hamiltonian cycle in Tn=2t−1 ⟨1, 3, 6; t⟩ is given by (1, 2)∪P2→6 ∪P6→10 ∪
· · · ∪ Pt−8→t−4 ∪ (t − 4, t + 2, t + 3, 3, 4) ∪ P4→8 ∪ P8→12 ∪ · · · ∪ Pt−6→t−2 ∪ (t − 2, t + 4, t +
5, . . . , n − 2, n − 1, n, n − t = t − 1, t, t + 1, 1). See Figure 12 for an illustration.
(iv) If t ≡ 3 mod 4, a Hamiltonian cycle in Tn=2t−1 ⟨1, 3, 6; t⟩ is given by (1, 2)∪P2→6 ∪P6→10 ∪
· · · ∪ Pt−9→t−5 ∪ (t − 5, t − 2, t + 4, t + 5, . . . , n − 2, n − 1, n, n − t = t − 1, t + 2, t + 3, 3, 4) ∪
P4→8 ∪ P8→12 ∪ · · · ∪ Pt−3→t+1 ∪ (t + 1, 1). See Figure 13 for an illustration.
The Hamiltonian cycles in Tn=(2t−1) ⟨1, 3, 6; t⟩ that contain the edge (n-2, n-1) can be extended
to cycles in T(2t−1)+(t−1) ⟨1, 3, 6; t⟩ while preserving this property. Suppose that for some nonnegative integer r, the graph Tn=(2t−1)+r(t−1) ⟨1, 3, 6; t⟩ has a Hamiltonian cycle containing the
edge (n-2, n-1). Then, by Remark 1.1, the graph Tn+t−1 ⟨1, 3, 6; t⟩ also has a Hamiltonian cycle
with the same property. Thus, Tn ⟨1, 3, 6; t⟩ is Hamiltonian for all n ≡ 1 mod (t − 1).
Case 3. n ≡ 2 mod (t − 1).
The smallest n in this case is t+1. A Hamiltonian cycle in Tn=t+1 ⟨1, 3, 6; t⟩ is given by (1, 2, 3, . . . , n−
2, n − 1, n, 1), which contains the edge (n − 2, n − 1). Suppose that for some non-negative integer
r, the graph Tn=(t+1)+r(t−1) ⟨1, 3, 6; t⟩ has a Hamiltonian cycle containing the edge (n − 2, n − 1).
150

www.ejgta.org

Hamiltonicity in directed Toeplitz graphs Tn ⟨1, 3, 6; t⟩

|

Shabnam Malik

...
2

1

4

3

6

5

8

7

9

10 11

12 13

14 15

16

17

18 19 20 21

31

30

Figure 10. A Hamiltonian cycle in T31 ⟨1, 3, 6; 16⟩.

...
1

2

3

4

5

6

7

8

9

10 11

12 13

14 15

16

17

18 19 20 21 22

30 33

Figure 11. A Hamiltonian cycle in T33 ⟨1, 3, 6; 17⟩.

Then, by Remark 1.1, the graph Tn+t−1 ⟨1, 3, 6; t⟩ also preserves this property. Thus, Tn ⟨1, 3, 6; t⟩
is Hamiltonian for all n ≡ 2 mod (t − 1).
Case 4. n ≡ 4 mod (t − 1).
The smallest n in this case is t + 3. We analyze values of t mod 4.
(i) If t ≡ 0 mod 4 and t ̸= 12, then a Hamiltonian cycle in Tn=t+3 ⟨1, 3, 6; t⟩ is (1, 2) ∪ P2→6 ∪
P6→10 ∪ · · · ∪ Pt−18→t−14 ∪ (t − 14, t − 8, t − 7, t − 6, t − 5, t − 4, t + 2, n = t + 3, 3, 4) ∪ P4→8 ∪
P8→12 ∪ · · · ∪ Pt−16→t−12 ∪ (t − 12, t − 11, t − 10, t − 9, t − 3, t − 2, t − 1, t, t + 1, 1), as illustrated
in Figure 14.
A Hamiltonian cycle in T15 ⟨1, 3, 6; 12⟩ is given by (1, 7, 10, 11, 14, 2, 8, 9, 15, 3, 4, 5, 6, 12, 13, 1).
(ii) If t ≡ 1 mod 4, a Hamiltonian cycle in Tn=t+3 ⟨1, 3, 6; t⟩ is given by (1, 2) ∪ P2→6 ∪ P6→10 ∪
· · · ∪ Pt−11→t−7 ∪ (t − 7, t − 6, t − 5, t − 4, t + 2, n = t + 3, 3, 4) ∪ P4→8 ∪ P8→12 ∪ · · · ∪ Pt−13→t−9 ∪
(t − 9, t − 3, t − 2, t − 1, t, t + 1, 1), see Figure 15.
(iii) If t ≡ 2 mod 4, a Hamiltonian cycle in Tn=t+3 ⟨1, 3, 6; t⟩ is given by (1, 2)∪P2→6 ∪P6→10 ∪
· · ·∪Pt−8→t−4 ∪(t−4, t+2, n = t+3, 3, 4)∪P4→8 ∪P8→12 ∪· · ·∪Pt−6→t−2 ∪ (t−2, t−1, t, t+1, 1),
as illustrated in Figure 16.
(iv) If t ≡ 3 mod 4, a Hamiltonian cycle in Tn=t+3 ⟨1, 3, 6; t⟩ is given by (1, 2) ∪ P2→6 ∪ P6→10 ∪
· · · ∪ Pt−1→t+3 ∪ (t + 3, 3, 4) ∪ P4→8 ∪ P8→12 ∪ · · · ∪ Pt−3→t+1 ∪ (t + 1, 1), as illustrated in Figure
17.
All these Hamiltonian cycles in Tn=t+3 ⟨1, 3, 6; t⟩ do not contain the edge (n-2, n-1). The next
representative in this class is n = 2t + 2. We again analyze values of t mod 4.
(i) If t ≡ 0 mod 4, a Hamiltonian cycle in Tn=2t+2 ⟨1, 3, 6; t⟩ is given by P1→5 ∪ P5→9 ∪ · · · ∪
Pt−11→t−7 ∪ (t − 7, t − 1, t, t + 3, t + 4, . . . , n − 2, n − 1, n, n − t = t + 2, 2, 3) ∪ P3→7 ∪ P7→11 ∪
· · · ∪ Pt−9→t−5 ∪ (t − 5, t − 4, t − 3, t − 2, t + 1, 1), as illustrated in Figure 18.
(ii) If t ≡ 1 mod 4, a Hamiltonian cycle in Tn=2t+2 ⟨1, 3, 6; t⟩ is given by P1→5 ∪ P5→9 ∪ · · · ∪
Pt→t+4 ∪ (t + 4, t + 5, . . . , n − 2, n − 1, n, n − t = t + 2, 2, 3) ∪ P3→7 ∪ P7→11 ∪ · · · ∪ Pt−6→t−2 ∪
(t − 2, t + 1, 1), as illustrated in Figure 19.
(iii) If t ≡ 2 mod 4, a Hamiltonian cycle in Tn=2t+2 ⟨1, 3, 6; t⟩ is given by P1→5 ∪ P5→9 ∪ · · · ∪
Pt−5→t−1 ∪ (t − 1, t + 5, t + 6)) ∪ Pt+6→t+10 ∪ Pt+10→t+14 ∪ · · · ∪ Pn−10→n−6 ∪ (n − 6, n, n − t =

151

www.ejgta.org

Hamiltonicity in directed Toeplitz graphs Tn ⟨1, 3, 6; t⟩

|

Shabnam Malik

...
1

2

4

3

7

6

5

8

9 10

11 12 13

14 15

16 17

18 19

26 27

20

Figure 12. A Hamiltonian cycle in T27 ⟨1, 3, 6; 14⟩.

...
1

2

4

3

6

5

7

8

9 10

11 12 13 14

15

16

17

18

19 20

28 29

Figure 13. A Hamiltonian cycle in T29 ⟨1, 3, 6; 15⟩.

1

2

3

4

5

7

8

9

10 11 12 13

14 15 16

17 18 19

Figure 14. A Hamiltonian cycle in T19 ⟨1, 3, 6; 16⟩.

t + 2, 2, 3) ∪ P3→7 ∪ P7→11 ∪ · · · ∪ Pt−7→t−3 ∪ (t − 3, t, t + 3, t + 4) ∪ Pt+4→t+8 ∪ Pt+8→t+12 ∪
· · · ∪ Pn−8→n−4 ∪ (n − 4, n − 3, n − 2, n − 1, n − 1 − t = t + 1, 1). See Figure 20 for reference.
(iv) If t ≡ 3 mod 4, a Hamiltonian cycle in Tn=2t+2 ⟨1, 3, 6; t⟩ is given by P1→5 ∪ P5→9 ∪ · · · ∪
Pt−14→t−10 ∪ (t − 10, t − 4, t − 3, t − 2, t − 1, t, t + 3, t + 4, . . . , n − 2, n − 1, n, n − t = t + 2, 2, 3) ∪
P3→7 ∪ P7→11 ∪ · · · ∪ Pt−16→t−8 ∪ (t − 8, t − 7, t − 6, t − 5, t + 1, 1), see Figure 21 for reference.
Since, in all these cases, the edge (n-2, n-1) appears in the Hamiltonian cycles of T2t+2 ⟨1, 3, 6; t⟩,
the cycle can be extended to a Hamiltonian cycle in T2t+2+(t−1) ⟨1, 3, 6; t⟩. Thus, by applying
the technique described in Remark 1.1, we conclude that Tn ⟨1, 3, 6; t⟩ is Hamiltonian for all
n ≡ 4 mod (t − 1).
Case 5. n ≡ t − 8 mod (t − 1).
Clearly, this applies for t ≥ 13, since the cases for t ∈ {10, 12}, have already been analyzed in
Cases 2 and Case 4, respectively. The smallest possible n satisfying this condition is n = 2t − 9.
We analyze values of t mod 4.
(i) If t ≡ 0 mod 4, a Hamiltonian cycle in Tn=2t−9 ⟨1, 3, 6; t⟩ is given by P1→5 ∪ P5→9 ∪ · · · ∪
Pt−15→t−11 ∪ (t − 11, t − 10, t − 4, t + 2, 2, 3) ∪ P3→7 ∪ P7→11 ∪ · · · ∪ Pt−17→t−13 ∪ (t − 13, t −
7, t − 6, t − 3, t − 2, t − 1, t, t + 3, t + 4, . . . , n − 2, n − 1, n, n − t = t − 9, t − 8, t − 5, t + 1, 1),
see Figure 22 for reference.
(ii) If t ≡ 1 mod 4 and t ̸= 13, a Hamiltonian cycle in Tn=2t−9 ⟨1, 3, 6; t⟩ is given by P1→5 ∪
P5→9 ∪· · ·∪Pt−16→t−12 ∪(t−12, t−11, t−5, t−4, t−3, t+3, t+4, t+5)∪Pt+5→t+9 ∪Pt+9→t+13 ∪
· · · ∪ Pn−7→n−3 ∪ (n − 3, n, n − t = t − 9, t − 6, t, t + 6, t + 7) ∪ Pt+7→t+11 ∪ Pt+11→t+15 ∪ · · · ∪
Pn−5→n−1 ∪ (n − 1, n − 1 − t = t − 10, t − 7, t − 1, t + 2, 2, 3) ∪ P3→7 ∪ P7→11 ∪ · · · ∪ Pt−18→t−14 ∪
(t − 14, t − 8, t − 2, t + 1, 1), see Figure 23 for reference.
For t = 13, a Hamiltonian cycle in T17 ⟨1, 3, 6; 13⟩ is (1, 7, 10, 16, 3, 9, 15, 2, 8, 11, 17, 4, 5, 6, 12, 13, 14, 1),
152

www.ejgta.org

Hamiltonicity in directed Toeplitz graphs Tn ⟨1, 3, 6; t⟩

3

2

1

4

6

5

7

9

8

10 11 12

13

14 15

16 17

|

Shabnam Malik

18 19 20

Figure 15. A Hamiltonian cycle in T20 ⟨1, 3, 6; 17⟩.

3

2

1

7

6

5

4

9

8

10

11 12 13

14

15 16 17

18 19 20

21

Figure 16. A Hamiltonian cycle in T21 ⟨1, 3, 6; 18⟩.

1

2

3

4

5

6

7

8

9

10 11 12 13

14 15 16

17

18 19 20 21 22

Figure 17. A Hamiltonian cycle in T22 ⟨1, 3, 6; 19⟩.

which does not contain the edge (15, 16). The next representative in this class is n = 29, where a
Hamiltonian cycle in T29 ⟨1, 3, 6; 13⟩ is (1, 4, 5, 8, 9, 10, 11, 12, 18, 19, 20, 21, 22, 25, 26, 29, 16, 17, 23, 24, 27, 28, 15
which contains the edge (27, 28).
(iii) If t ≡ 2 mod 4 and t ̸= 14, a Hamiltonian cycle in Tn=2t−9 ⟨1, 3, 6; t⟩ is given by P1→5 ∪
P5→9 ∪· · ·∪Pt−21→t−17 ∪(t−17, t−11, t−10, t−7, t−1, t, t+3, t+4, . . . , n−2, n−1, n, n−t =
t − 9, t − 8, t − 5, t − 4, t + 2, 2, 3) ∪ P3→7 ∪ P7→11 ∪ · · · ∪ Pt−19→t−15 ∪ (t − 15, t − 14, t − 13, t −
12, t − 6, t − 3, t − 2, t + 1, 1), see Figure 24.
For t = 14, a Hamiltonian cycle in T19 ⟨1, 3, 6; 14⟩ is (1, 7, 13, 19, 5, 8, 11, 14, 17, 18, 4, 10, 16, 2, 3, 6, 9, 12, 15, 1
(iv) If t ≡ 3 mod 4, a Hamiltonian cycle in Tn=2t−9 ⟨1, 3, 6; t⟩ is given by P1→5 ∪ P5→9 ∪ · · · ∪
Pt−14→t−10 ∪ (t − 10, t − 7, t − 1, t, t + 3, t + 4, . . . , n − 2, n − 1, n, n − t = t − 9, t − 8, t − 5, t −
4, t + 2, 2, 3) ∪ P3→7 ∪ P7→11 ∪ · · · ∪ Pt−16→t−12 ∪ (t − 12, t − 6, t − 3, t − 2, t + 1, 1), see Figure
25.
All these Hamiltonian cycles in Tn ⟨1, 3, 6; t⟩, which contain the edge (n-2, n-1), can be extended to Hamiltonian cycles in Tn+(t−1) ⟨1, 3, 6; t⟩. Thus, by applying the technique from Remark
1.1, it follows that Tn ⟨1, 3, 6; t⟩ is Hamiltonian for all n ≡ t − 8 mod (t − 1).
Case 6. n ≡ t − 5 mod (t − 1).
The smallest n in this case is n = 2t − 6. We analyze values of t mod 4.
(i) If t ≡ 0 mod 4, a Hamiltonian cycle in Tn=2t−6 ⟨1, 3, 6; t⟩ is given by P1→5 ∪ P5→9 ∪ · · · ∪
Pt−11→t−7 ∪ (t − 7, t − 1, t, t + 3, t + 4, . . . , n − 2, n − 1, n, n − t = t − 6, t − 5, t − 4, t + 2, 2, 3) ∪
P3→7 ∪ P7→11 ∪ · · · ∪ Pt−13→t−9 ∪ (t − 9, t − 3, t − 2, t + 1, 1), see Figure 26.
(ii) If t ≡ 1 mod 4, a Hamiltonian cycle in Tn=2t−6 ⟨1, 3, 6; t⟩ is P1→5 ∪P5→9 ∪· · ·∪Pt−12→t−8 ∪
153

www.ejgta.org

Hamiltonicity in directed Toeplitz graphs Tn ⟨1, 3, 6; t⟩

|

Shabnam Malik

...
2

1

4

3

6

5

8

7

9 10

11 12 13 14

15

16 17

25 26

Figure 18. A Hamiltonian cycle in T26 ⟨1, 3, 6; 12⟩.

...
1

2

3

4

5

6

7

8

9

10 11

12 13

14 15

16 17 18

27 28

Figure 19. A Hamiltonian cycle in T28 ⟨1, 3, 6; 13⟩.

(t − 8, t − 5, t − 2, t − 1, t + 2, 2, 3) ∪ P3→7 ∪ P7→11 ∪ · · · ∪ Pt−14→t−10 ∪ (t − 10, t − 7, t − 4, t −
3, t + 3, t + 4, . . . , n − 2, n − 1, n, n − t = t − 6, t, t + 1, 1), see Figure 27.
(iii) If t ≡ 2 mod 4 and t ̸= 10, a Hamiltonian cycle in Tn=2t−6 ⟨1, 3, 6; t⟩ is P1→5 ∪ P5→9 ∪
· · · ∪ Pt−13→t−9 ∪ (t − 9, t − 3, t + 3, t + 4, t + 5) ∪ Pt+5→t+9 ∪ Pt+9→t+13 ∪ · · · ∪ Pn−7→n−3 ∪ (n −
3, n, n − t = t − 6, t, t + 6, t + 7) ∪ Pt+7→t+11 ∪ Pt+11→t+15 ∪ · · · ∪ Pn−5→n−1 ∪ (n − 1, n − 1 − t =
t − 7, t − 4, t − 1, t + 2, 2, 3) ∪ P3→7 ∪ P7→11 ∪ · · · ∪ Pt−15→t−11 ∪ (t − 11, t − 8, t − 5, t − 2, t + 1, 1),
see Figure 28.
For t = 10, a Hamiltonian cycle in T14 ⟨1, 3, 6; 10⟩ is (1, 7, 10, 13, 3, 6, 9, 12, 2, 8, 14, 4, 5, 11, 1),
which does not contain the edge (12, 13). The next representative in this class is n = 23, where a
Hamiltonian cycle in T23 ⟨1, 3, 6; 10⟩ is (1, 2, 8, 14, 20, 21, 22, 12, 18, 19, 9, 15, 16, 17, 23, 13, 3, 4, 5,
6, 7, 10, 11, 1), which contains the edge (21, 22).
(iv) If t ≡ 3 mod 4, a Hamiltonian cycle in Tn=2t−6 ⟨1, 3, 6; t⟩ is P1→5 ∪P5→9 ∪· · ·∪Pt−18→t−14 ∪
(t − 14, t − 8, t − 7, t − 1, t, t + 3, t + 4, . . . , n − 2, n − 1, n, n − t = t − 6, t − 5, t − 4, t + 2, 2, 3) ∪
P3→7 ∪ P7→11 ∪ · · · ∪ Pt−16→t−12 ∪ (t − 12, t − 11, t − 10, t − 9, t − 3, t − 2, t + 1, 1), see Figure
29.
All these Hamiltonian cycles in Tn ⟨1, 3, 6; t⟩, which include the edge (n-2, n-1), can be extended to form Hamiltonian cycles in Tn+(t−1) ⟨1, 3, 6; t⟩. Therefore, by applying the technique
from Remark 1.1, Tn ⟨1, 3, 6; t⟩ is Hamiltonian for all n ≡ t − 5 mod (t − 1).
Case 7. n ≡ t − 4 mod (t − 1).
The smallest possible value of n is n = 2t − 5. We analyze values of t mod 4.
(i) If t ≡ 0 mod 4, a Hamiltonian cycle in Tn=2t−5 ⟨1, 3, 6; t⟩ is P1→5 ∪ P5→9 ∪ · · · ∪ Pt−11→t−7 ∪
(t − 7, t − 1, t, t + 3, t + 4, . . . , n − 2, n − 1, n, n − t = t − 5, t − 4, t + 2, 2, 3) ∪ P3→7 ∪ P7→11 ∪
· · · ∪ Pt−13→t−9 ∪ (t − 9, t − 6, t − 3, t − 2, t + 1, 1), see Figure 30.
(ii) If t ≡ 1 mod 4 and t ∈
/ {13, 17}, a Hamiltonian cycle in Tn=2t−5 ⟨1, 3, 6; t⟩ is P1→5 ∪ P5→9 ∪
· · ·∪Pt−20→t−16 ∪(t−16, t−15, t−14, t−13, t−7, t−6, t−3, t+3, t+4, . . . , n−2, n−1, n, n−t =
t − 5, t − 4, t + 2, 2, 3) ∪ P3→7 ∪ P7→11 ∪ · · · ∪ Pt−22→t−18 ∪ (t − 18, t − 12, t − 11, t − 10, t −
9, t − 8, t − 2, t − 1, t, t + 1, 1), see Figure 31.
For t ∈ {13, 17}, Hamiltonian cycles in T21 ⟨1, 3, 6; 13⟩ and T29 ⟨1, 3, 6; 17⟩ are (1, 4, 7, 10,
154

www.ejgta.org

Hamiltonicity in directed Toeplitz graphs Tn ⟨1, 3, 6; t⟩

1

2

3

4

5

6

8

7

9

10 11

12 13 14 15

16 17 18

|

19

Shabnam Malik

20 21

22

Figure 20. A Hamiltonian cycle in T22 ⟨1, 3, 6; 10⟩.

...
1

2

3

4

5

6

7

8

9

10

11

12 13

14 15

16

17

18 19 20

31 32

Figure 21. A Hamiltonian cycle in T32 ⟨1, 3, 6; 15⟩.

13, 16, 3, 6, 9, 12, 15, 2, 5, 11, 17, 18, 19, 20, 21, 8, 14, 1) and (1, 4, 7, 10, 13, 16, 19, 2, 5, 8, 11, 14,
17, 20, 3, 6, 9, 15, 21, 22, 23, 24, 25, 26, 27, 28, 29, 12, 18, 1), respectively.
(iii) If t ≡ 2 mod 4 and t ̸= 10, a Hamiltonian cycle in Tn=2t−5 ⟨1, 3, 6; t⟩ is P1→5 ∪ P5→9 ∪ · · · ∪
Pt−17→t−13 ∪ (t − 13, t − 7, t − 6, t − 3, t + 3, t + 4, . . . , n − 2, n − 1, n, n − t = t − 5, t − 4, t +
2, 2, 3) ∪ P3→7 ∪ P7→11 ∪ · · · ∪ Pt−15→t−11 ∪ (t − 11, t − 10, t − 9, t − 8, t − 2, t − 1, t, t + 1, 1),
see Figure 32.
For t = 10, a Hamiltonian cycle in T15 ⟨1, 3, 6; 10⟩ is (1, 2, 8, 14, 15, 5, 6, 9, 12, 13, 3, 4, 7, 10, 11,
1), which does not include the edge (13, 14). The next representative in this class is n = 24, where
a Hamiltonian cycle in T24 ⟨1, 3, 6; 10⟩ is (1, 2, 3, 4, 5, 6, 12, 15, 18, 24, 14, 20, 21, 22, 23, 13, 19, 9,
10, 16, 17, 7, 8, 11, 1) which includes the edge (22, 23).
(iv) If t ≡ 3 mod 4, a Hamiltonian cycle in Tn=2t−5 ⟨1, 3, 6; t⟩ is P1→5 ∪P5→9 ∪· · ·∪Pt−10→t−6 ∪
(t − 6, t − 3, t + 3, t + 4, . . . , n − 2, n − 1, n, n − t = t − 5, t − 4, t + 2, 2, 3) ∪ P3→7 ∪ P7→11 ∪
· · · ∪ Pt−12→t−8 ∪ (t − 8, t − 2, t − 1, t, t + 1, 1), see Figure 33.
All Hamiltonian cycles in Tn ⟨1, 3, 6; t⟩ that include the edge (n-2, n-1) can be extended to
Hamiltonian cycles in Tn+(t−1) ⟨1, 3, 6; t⟩. Thus, by applying the technique from Remark 1.1,
Tn ⟨1, 3, 6; t⟩ is Hamiltonian for all n ≡ t − 4 mod (t − 1).
Case 8. n ≡ s mod (t − 1), where s ∈ {0, 1, 2, . . . , t − 2} \ {0, 1, 2, 4, t − 8, t − 5, t − 4}. The
smallest n for each s is n = s + t − 1. We further analyze values of n mod 4, with even and odd t.
(i) If (n ≡ 0 mod 4 and t is even) or (n ≡ 2 mod 4 and t is odd). Then a Hamiltonian cycle
in Tn ⟨1, 3, 6; t⟩ is (1, 2, . . . , s − 2) ∪ Ps−2→s+2 ∪ Ps+2→s+6 ∪ · · · ∪ Pt−5→t−1 ∪ (t − 1, t + 2, t +
3, . . . , n − 2, n − 1, n, n − t = s − 1, s) ∪ Ps→s+4 ∪ Ps+4→s+8 ∪ · · · ∪ Pt−3→t+1 ∪ (t + 1, 1), see
Figure 34.
(ii) If (n ≡ 1 mod 4 and t is even) or (n ≡ 3 mod 4 and t is odd), then a Hamiltonian cycle in
Tn ⟨1, 3, 6; t⟩ is (1, 2, . . . , s−2)∪Ps−2→s+2 ∪Ps+2→s+6 ∪· · ·∪Pt−8→t−4 ∪(t−4, t+2, t+3, . . . , n−
2, n − 1, n, n − t = s − 1, s) ∪ Ps→s+4 ∪ Ps+4→s+8 ∪ · · · ∪ Pt−6→t−2 ∪ (t − 2, t − 1, t, t + 1, 1),
see Figure 35.
(iii) If (n ≡ 2 mod 4 and t is even) or (n ≡ 0 mod 4 and t is odd), then a Hamiltonian cycle in
Tn ⟨1, 3, 6; t⟩ is (1, 2, . . . , s − 2) ∪ Ps−2→s+2 ∪ Ps+2→s+6 ∪ · · · ∪ Pt−15→t−11 ∪ (t − 11, t − 5, t −
4, t + 2, t + 3, . . . , n − 2, n − 1, n, n − t = s − 1, s) ∪ Ps→s+4 ∪ Ps+4→s+8 ∪ · · · ∪ Pt−13→t−9 ∪
155

www.ejgta.org

Hamiltonicity in directed Toeplitz graphs Tn ⟨1, 3, 6; t⟩

|

Shabnam Malik

...
1

2

3

4

5

6

8

7

10 11 12

9

13 14

15

16 17 18 19 20

30

31

22 23 24

25

21 22 23 24

Figure 22. A Hamiltonian cycle in T31 ⟨1, 3, 6; 20⟩.

16

10
1

2

3

4

5

6

7

8

9

11 12 13 14 15

17

18

19 20 21

Figure 23. A Hamiltonian cycle in T25 ⟨1, 3, 6; 17⟩.

(t − 9, t − 8, t − 7, t − 6, t − 3, t − 2, t − 1, t, t + 1, 1), see Figure 36.
(iv) If (n ≡ 3 mod 4 and t is even) or (n ≡ 1 mod 4 and t is odd), then a Hamiltonian cycle in
Tn ⟨1, 3, 6; t⟩ is (1, 2, . . . , s − 2) ∪ Ps−2→s+2 ∪ Ps+2→s+6 ∪ · · · ∪ Pt−18→t−14 ∪ (t − 14, t − 8, t −
7, t − 6, t − 5, t − 4, t + 2, t + 3, . . . , n − 2, n − 1, n, n − t = s − 1, s) ∪ Ps→s+4 ∪ Ps+4→s+8 ∪
· · · ∪ Pt−16→t−12 ∪ (t − 12, t − 11, t − 10, t − 9, t − 3, t − 2, t − 1, t, t + 1, 1), see Figure 37.
Since in all these cases the edge (n-2, n-1) is present in the Hamiltonian cycles of Tn ⟨1, 3, 6; t⟩,
applying the technique from Remark 1.1 ensures that Tn ⟨1, 3, 6; t⟩ remains Hamiltonian for all
n ≡ s mod (t − 1), where s ∈ {0, 1, 2, . . . , t − 2} \ {0, 1, 2, 4, t − 8, t − 5, t − 4}.
This completes the proof.
Conjectures and concluding remark
We propose the following conjectures.
1. Tn ⟨1, 3, 6; 2⟩ is non-Hamiltonian for n ≡ 2 mod 4.
2. Tn ⟨1, 3, 6; 3⟩ is non-Hamiltonian for n ∈ {7, 8, 9, 12, 14, 16}.
3. T12 ⟨1, 3, 6; 4⟩ is non-Hamiltonian.
4. Tn ⟨1, 3, 6; 6⟩ is non-Hamiltonian for n ∈ {10, 14}.
5. Tn ⟨1, 3, 6; 7⟩ is non-Hamiltonian for n ∈ {9, 12}.
6. T10 ⟨1, 3, 6; 8⟩, T13 ⟨1, 3, 6; 9⟩ and T13 ⟨1, 3, 6; 11⟩ are non-Hamiltonian.
The next step, in our view, is to complete the investigation of Hamiltonicity in Toeplitz graphs
Tn ⟨1, 3, 6, s4 , s5 , . . . , sk ; t1 , t2 , . . . , tl ⟩ by solving the stated conjectures.
Acknowledgement
I would like to sincerely thank the referee for their valuable comments and suggestions.
156

www.ejgta.org

Hamiltonicity in directed Toeplitz graphs Tn ⟨1, 3, 6; t⟩

19

16
1

2

3

4

5

8 9 10 11 12 13 14

6 7

15

17 18

|

23
20 21 22

Shabnam Malik

...
24 25 26
34 35

Figure 24. A Hamiltonian cycle in T35 ⟨1, 3, 6; 22⟩.

16

13
1

2

3

4

5

6

7

8

9

10 11

12

14 15

...
17

18 19 20 21 22 23

28 29

Figure 25. A Hamiltonian cycle in T29 ⟨1, 3, 6; 19⟩.

References
[1] M. Anholcer, M. Kalkowski, and J. Przybylo, A new upper bound for the total vertex irregularity strength of graphs, Discrete Math., 309 (2009), 6316–6317.
[2] A. Ahmad, M. Baca, and M.F. Nadeem, On edge irregularity strength of Toeplitz graphs,
UPB. Sci. Bull., Ser. A., 78(4) (2016), 155–162.
[3] A. Ahmad, F. Nadeem, and A. Gupta, On super edge-magic deficiency of certain Toeplitz
graphs, Hacet J Math Stat., 47(3) (2018), 513–519.
[4] S. Akbari, S. H. Ghorban, S. Malik, and S. Qajar, Conditions for regularity and for 2connectivity of Toeplitz graphs, Util. Math., 110 (2019), 305–314.
[5] L. Aslam, S. Sarwar, M.J. Yousaf, and S. Waqar, Cycle discrepancy of cubic Toeplitz graphs,
Pak. J. Eng. Appl. Sci., 22 (2018), 14–19.
[6] S. Bau, A generalization of the concept of Toeplitz graphs, Mong. Math. J., 15 (2011), 54–61.
[7] M. Baca, Y. Bashir, F. Nadeem, and A. Shabbir, On super edge-antimagic total labeling of
Toeplitz graphs, Springer Proc. Math. Stat., 98 (2015), 1–10.
[8] F. Boesch and R. Tindell, Circulants and their connectivities, J. Graph Theory, 8 (1984),
487–499.
[9] Z.R. Bogdanowicz, Hyper-hamiltonian circulants, Electron. J. Graph Theory Appl., 9(1)
(2021), 185–193.
[10] R.E. Burkard and W. Sandholzer, Efficiently solvable special cases of bottleneck travelling
salesman problems, Discrete Appl. Math., 32 (1991), 61–67.
157

www.ejgta.org

Hamiltonicity in directed Toeplitz graphs Tn ⟨1, 3, 6; t⟩

11
1

2

3

4

5

6

8

7

9

10

|

Shabnam Malik

17
12 13 14 15 16

...
18

19 20 21 22 23 24

33 34

Figure 26. A Hamiltonian cycle in T34 ⟨1, 3, 6; 20⟩.

10
1

2

3

4

5

6

7

8

9

14
11

12

13

15

...
16 17 18 19 20 21

27 28

Figure 27. A Hamiltonian cycle in T28 ⟨1, 3, 6; 17⟩.

[11] E.A. van Doorn, Connectivity of circulant digraphs, J. Graph Theory, 10 (1986), 9–14.
[12] R. van Dal, G. Tijssen, Z. Tuza, J.A.A. van der Veen, Ch. Zamfirescu, and T. Zamfirescu,
Hamiltonian properties of Toeplitz graphs, Discrete Math., 159 (1996), 69–81.
[13] R. Euler, Coloring infinite, planar Toeplitz graphs, Tech. Report, LIBr, 1998.
[14] R. Euler, Characterizing bipartite Toeplitz graphs, Theor. Comput. Sci., 263 (2001), 47–58.
[15] R. Euler, Coloring planar Toeplitz graphs and the stable set polytope, Discrete Math., 276
(2004), 183–200.
[16] R. Euler and T. Zamfirescu, On planar Toeplitz graphs, Graphs Comb., 29 (2013), 1311–
1327.
[17] R. Euler, H. LeVerge, and T. Zamfirescu, A characterization of infinite, bipartite Toeplitz
graphs, in: Ku Tung-Hsin (Ed.), Comb. Graph Theory., 1 (1995), Academia Sinica, World
Scientific, Singapore, 119–130.
[18] C. Heuberger, On hamiltonian Toeplitz graphs, Discrete Math., 245 (2002), 107–125.
[19] S.H. Ghorban, Toeplitz graph decomposition, Trans. Comb., 1(4) (2012), 35–41.
[20] A. Ilic and M. Basic, On the chromatic number of integral circulant graphs, Comput. Math.
Appl., 60(1) (2010), 144–150.
[21] M. Klin, V. Liskovets, and R. Poschel, Analytical enumeration of circulant graphs with primesquared number of vertices, Sem. Lotharing Combin., 36 (1996), 1–36.
158

www.ejgta.org

Hamiltonicity in directed Toeplitz graphs Tn ⟨1, 3, 6; t⟩

9

5
2

1

3

4

6

15
10 11 12 13

8

7

21

18
16

17

19

20

|

Shabnam Malik

25
23 24

26 27 28 29 30

Figure 28. A Hamiltonian cycle in T30 ⟨1, 3, 6; 18⟩.

10
1

2

3

4

5

6

7

8

9

16
11 12 13 14 15

...
17 18 19 20 21 22 23

31

32

Figure 29. A Hamiltonian cycle in T32 ⟨1, 3, 6; 19⟩.

[22] J.B. Liu, M.F. Nadeem, H.M.A. Siddiqui, and W. Nazir, Computing metric dimension of
certain families of Toeplitz graphs, IEEE Access, 7 (2019), 126734–126741.
[23] M. Muzychuk, A solution of the isomorphism problem for circulant graphs, Proc. London
Math. Soc., 88(1) (2004), 1–41.
[24] S. Malik, Hamiltonicity in directed Toeplitz graphs of maximum (out or in) degree 4, Util.
Math., 89 (2012), 33–68.
[25] S. Malik, Hamiltonian cycles in directed Toeplitz graphs-part 2, Ars Comb., 116 (2014), 303319.
[26] S. Malik, Hamiltonian cycles in directed Toeplitz graphs Tn ⟨1, 2; t1 ≤ 5, t2 ⟩, Util. Math., 99
(2016), 3–17.
[27] S. Malik, Hamiltonicity in directed Toeplitz graphs Tn ⟨1, 2, t1 , t2 ⟩, Australas. J. Combin.,
78(3) (2020), 434–449.
[28] S. Malik, Corrigendum and extension to ’Hamiltonicity in directed Toeplitz graphs
Tn ⟨1, 2, t1 , t2 ⟩’, Australas. J. Combin., 83(1) (2022), 173–175.
[29] S. Malik, Hamiltonicity in directed Toeplitz graphs Tn ⟨1, 3, 4; t⟩, Bull. Math. Soc. Sci. Math.
Roumanie., 64(112)(4) (2021), 317–327.
[30] S. Malik, Hamiltonicity in directed Toeplitz graphs with s1 = 1 and s3 = 4, Comput. Math.
Methods., 2023, Article ID 3676487, 11 pages.
[31] S. Malik, Hamiltonicity in directed Toeplitz graphs Tn ⟨1, 3; 1, t⟩, Bull. Math. Soc. Sci. Math.
Roumanie., 66(114)(3) (2023), 307–318.
159

www.ejgta.org

Hamiltonicity in directed Toeplitz graphs Tn ⟨1, 3, 6; t⟩

3

10

7
4

2

1

5

6

8

13
11 12

9

|

17
14 15 16

Shabnam Malik

...
18 19 20

26

27

Figure 30. A Hamiltonian cycle in T27 ⟨1, 3, 6; 16⟩.

4
1

2

3

8
5

6 7

9

13
10 11 12

15
14

18
16 17

23
19

20

21 22

...
24 25

36 37

Figure 31. A Hamiltonian cycle in T37 ⟨1, 3, 6; 21⟩.

[32] S. Malik and A.M. Qureshi, Hamiltonian cycles in directed Toeplitz graphs, Ars Comb., 109
(2013), 511–526.
[33] S. Malik and A.M. Qureshi, Hamiltonicity in directed Toeplitz graphs Tn ⟨1, 3, 5; t⟩, Bull.
Math. Soc. Sci. Math. Roumanie., 67(115)(2) (2024), 239–252.
[34] S. Malik and F. Ramezani, Hamiltonicity in directed Toeplitz graphs having increasing edges
of length 1, 3 and 7, J. Prime Res. Math., 20(2) (2024), 64–76.
[35] S. Malik and T. Zamfirescu, Hamiltonian connectedness in directed Toeplitz graphs, Bull.
Math. Soc. Sci. Math. Roumanie., 53(101) (2010), 145–156.
[36] M.F. Nadeem, A. Shabbir, and T. Zamfirescu, Hamiltonian connectedness of Toeplitz graphs,
Springer Proc. Math. Stat., 98 (2015), 135–149.
[37] M.F. Nadeem, S. Qu, A. Ahmad, and M. Azeem, Metric dimension of some generalized
families of Toeplitz graphs, Math. Probl. Eng., (2022), Article ID 9155291, 10 pages.
[38] S. Nicoloso and U. Pietropaoli, On the chromatic number of Toeplitz graphs, Discrete Appl.
Math., 164(1) (2014), 286–296.
[39] I. Reiter and J. Zhou, Perfect matching transitivity of circulant graphs, Electron. J. Graph
Theory Appl., 8(2) (2020), 301–311.
[40] J.A.A. van der Veen, R. van Dal, and G. Sierksma, The symmetric circulant traveling salesman problem, Tech. Rep., 429 (1991), University of Groningen.
[41] Q.F. Yang, R.E. Burkard, and G.J. Woeginger, Hamiltonian cycles in circulant digraphs with
two stripes, Tech. Report., 20 (1995), Technical University Graz.

160

www.ejgta.org

Hamiltonicity in directed Toeplitz graphs Tn ⟨1, 3, 6; t⟩

|

Shabnam Malik

...
1

2

3

4

5

6

7

8

9

10 11 12 13 14 15 16 17 18 19

20 21 22

30

31

Figure 32. A Hamiltonian cycle in T31 ⟨1, 3, 6; 18⟩.

3
1

2

11

7
4

5

6

8

9

10

13
12

17
14 15 16

...
18 19

24

25

Figure 33. A Hamiltonian cycle in T25 ⟨1, 3, 6; 15⟩.

[42] H. Zafar, N. Akhter, M.K. Jamil, and F. Nadeem, Hamiltonian connectedness and Toeplitz
graphs, Am. Sci. Res. J. Eng. Technol. Sci., 33(1) (2017), 255–268.
[43] A. Zhou and X.D. Zhang, Enumeration of circulant graphs with order n and degree 4 or 5, J.
Univ. Electron. Sci. Technol. China, 25 (1996), 272–276.

161

www.ejgta.org

Hamiltonicity in directed Toeplitz graphs Tn ⟨1, 3, 6; t⟩

9
1

2

3

4

5

6

13

14

15

Shabnam Malik

20

16

12
10 11

8

7

|

17

18

19

21

22 23

24

Figure 34. A Hamiltonian cycle in T24 ⟨1, 3, 6; 18⟩, where s = 7.

2

1

3

4

5

8

7

6

9 10

11 12

13 14

15 16

20 21

17 18 19

22 23

24 25

Figure 35. A Hamiltonian cycle in T25 ⟨1, 3, 6; 18⟩, where s = 8.

1

2

3 4

5 6

9 10

8

7

11 12 13 14

15 16 17

18 19 20

22

24 25 26 27 28

Figure 36. A Hamiltonian cycle in T28 ⟨1, 3, 6; 23⟩, where s = 6

1

2

3 4

5 6

7

8

9

10 11 12 13 14

15 16 17 18 19 20

22

24 25

27 28 29

Figure 37. A Hamiltonian cycle in T29 ⟨1, 3, 6; 23⟩, where s = 7.

162

www.ejgta.org