255 
 

 American Scientific Research Journal for Engineering, Technology,  and Sciences  (ASRJETS) 

ISSN (Print) 2313-4410, ISSN (Online) 2313-4402 

© Global Society of Scientific Research and Researchers  

http://asrjetsjournal.org/  

 

Hamltonian Connectedness and Toeplitz Graphs 

Hassan Zafara, Naveed Akhter b*, Muhammad Kamran Jamilc, Faisal Nadeemd 

aNational College of Business & Administration, DHA Campus, Lahore 54590, Pakistan 

bGovt. Dyal Singh College, Lahore 54590 , Pakistan 

cRiphah Institute of Computing and Applied Sciences (RICAS) Riphah International University, Lahore 54590, 

Pakistan. , Pakistan 

dDepartment of Mathematics, COMSATS, Institute of Information and Technology, Lahore 54590, Pakistan 

aEmail:  hassanxfr@hotmail.com 

bEmail: akhtarnaweed@yahoo.com 

cEmail:  m.kamran.sms@gmail.com 

dEmail: faisal.nadeem@ciitlahore.edu.pk 

 

Abstract 

A square matrix of order n is called Toeplitz matrix if it has constant elements along all diagonals parallel to 

the main diagonal and a graph is called Toeplitz graph if its adjacency matrix is Toeplitz. In this paper we 

proved that the Toeplitz graphs 2,3, tnT , for 28n    and 
8

4
2

n
t


   are Hamiltonian  connected. 

Keywords: Hamiltonian graph; Hamiltonian connected; Toeplitz graph; Toeplitz matrix; Hamiltonian path.  

1. Introduction  

A square matrix of order n is called Toeplitz matrix if it has constant elements along all diagonals parallel 

to the main diagonal.  A simple undirected graph 
nT  with vertex set  1,2,3, ,n  is called a Toeplitz graph 

if its adjacency matrix is Toeplitz.  A Toeplitz graph is uniquely defined by the first row of its adjacency 

matrix. The first row of adjacency matrix of a Toeplitz graph is always a sequence of 0’s and 1’s. If the 

1’s in that sequence places at 1 2 31, 1, 1, , 1kt t t t     positions with 1 2 31 ,kt t t t n       we write 

1 2 3, , , ,n n kT T t t t t . In a Toeplitz graph 
1 2 3, , , ,n kT t t t t  two vertices a  and b  are connected by an edge 

if and only if  1 2 3, , , , ka b t t t t  . 

------------------------------------------------------------------------ 

* Corresponding author.  

http://asrjetsjournal.org/
mailto:example@yahoo.com


American Scientific Research Journal for Engineering, Technology, and Sciences (ASRJETS) (2017) Volume 33, No  1, pp 255-268 

256 
 

A graph G  of order n  is called Hamiltonian if it contains a cycle of order n . A graph G  of order n   is called 

traceable if it contains a path of order n  and such a path is called Hamiltonian path. The graph G  is called 

Hamiltonian connected if for any pair of distinct vertices a  and b  of G , there exists a Hamiltonian path 

with ends a  and b . Every Hamiltonian connected graph is Hamiltonian. 

Connectedness, bipartiteness, colourbality and planarity of Toeplitz graphs are discussed in [1, 2, 3, 4]. Some of the 

Hamiltonian properties of undirected Toeplitz graphs were discussed in [1] and [5].  The Hamiltonian properties of 

directed Toeplitz graphs were studied in [6, 7].  S. Malik and T. Zamfirescu investigated Hamiltonian 

properties of Toeplitz graphs in [8].  M. F. Nadeem Ayesha Shabbir and Tudor Zamfirescu complete the 

picture of  Toeplitz graphs 
1 2, , 1,3,n nT t t T t  and 1,5, tnT   in [9]. In this paper we proved that the Toeplitz 

graphs 2,3, tnT  are Hamiltonian connected for 28n   and 
8

4
2

n
t


  . 

Suppose T  is a Toeplitz graph and , , , ,l m k q n  are its vertices. If l m , then  , 1,P l l m  is a path with ends 

l   and 1l   that contains all vertices, , 1, 2, ,m m m l  . If m l  then  , 1,P l l m a path with ends l   and 

1l   that contains all vertices, , 1, 2, ,l l l m   . The path  ,P l m  has end vertices l and m and contains 

all vertices, , 1, 2, ,l l l m    except vertices  1l    and 1m . The path   ,H l m  has ends l  and m  and 

contains all vertices , 1, 2, ,l l l m   . The path  ' , ,P l m k  has end vertices l  and m , and contains all 

vertices , 1, 2, ,l l l m    except vertex  1, 1k l m   . The path  ,y

xH l m  has ends x ,y and contains 

vertices , 1, 2, ,l l l m   . The path  ,y

xh l m  has ends x  and y  contains all vertices , 1, 2, ,l l l m  

such that 5 , 5l x y m    . 

2. Preliminaries 

Lemma 2.1 The Toeplitz graph 2,3nT , n ≥ 6 admits Hamiltonian path  1,2,P n and  1, ,1P n n . 

Proof. The Toeplitz graph 
2 2,3nT has he following Hamiltonian path  1,2,P n . “1,3,5, ,2 7,n 2n 5,

2n 2,2n,2n 3,2n 1,2n 4,2n 6, 6,4,2.     ” 

The Toeplitz graph 
2 1 2,3nT 

 the Hamiltonian path “ 1,3,5, 2 5,2 3,2 ,2 2,n n n n   2 1,2 1,n n   2 4,n 

2 6, 6,4,2n ”   that connects 1 and 2. Due to symmetry of the Toeplitz graphs 2,3nT  has Hamiltonian path

 1, ,1P n n .  The Hamiltonian paths connecting 1 and 2 are shown in Fig. 1 and Fig. 2. 

Corollary 2.2 (a). In Toeplitz graphs 2,3nT , if l < m, then  , 1,mP l l   exists for 5.m l    

(b). In Toeplitz graphs 2,3nT , if l > m, then  , 1,mP l l  exists for 4.l m    



American Scientific Research Journal for Engineering, Technology, and Sciences (ASRJETS) (2017) Volume 33, No  1, pp 255-268 

257 
 

 

 

 

Figure 1: Hamiltonian Path with ends 1  and 2  

 

Figure 2: Hamiltonian Path with ends 1  and 2  

Lemma 2.3. The Toeplitz graph 2,3nT  for 8n   contains the path  1, .P n   

Proof. We divide the proof in following four cases.  

Case 1. If  0 mod 4n  , then 4n k  for 2.k   The required path is shown in Fig. 3.  

 

 

 

 

Figure 3: Path with ends 1 and 4k containing all vertices except 2 and 4 1k   

Case 2. If  1 mod 4 ,n   then n = 4k + 1 for k _ 2. The path that connects 1 with 4k + 1 and contains all the 

vertices in the Toeplitz graph 
4 1 2,3kT 

 except 2 and 4k is “1,4,6,3,5,8,10,7, ,4 6,4 9,4 7,k k k    4k 4,

4k 2,4k 5,4k 3,4k 1,4k 1     ”   and is shown in Fig. 4. 

Case 3. If n = 2 (mod 4), then n = 4k + 2 for 2n  . The path that connects 1 with 4k + 2 and contains all the 

vertices in the Toeplitz graph 
4 2 2,3kT 

, except 2 and 4k+1 is  

1,3,5,7,4,6,8,10,12,9,11,14,16,13,15,18, 4k 5 4 2,4 ,4 3,4 1,4 2k k k k k    " and is shown in Fig. 5. 



American Scientific Research Journal for Engineering, Technology, and Sciences (ASRJETS) (2017) Volume 33, No  1, pp 255-268 

258 
 

 

 

 

Figure 4: Path with ends 1 and 4k + 1 containing all vertices except 2 and 4k 

Case 4. If n = 3 (mod 4), then n = 4k + 3 for 2n  . The path that connects 1 with 4k + 3 and contains all the 

vertices in the Toeplitz graph 
4 3 2,3kT 

, except 2 and 4k + 2 is  “1,3,5,7,4,6,9,11,8,10,13, 4k 5,4k 8  , 

4 6,4 3,4 ,4 2,4 4,4 3,4 1,4 3k k k k k k k k       ” and is shown in Fig. 6. 

 

Figure 5: Path with ends 1 and 4k + 2 containing all vertices except 2 and 4k + 1 

 

 

 

Figure 6: Path with ends 1 and 4k + 3 containing all vertices except 2 and 4k + 2 

Corollary 2.4. The path  ,P l m  exists in Toeplitz graphs 2,3nT  for 7.m l    

Lemma 2.5. The Toeplitz graph 2,3nT , for  6n   and 8n    admits a Hamiltonian path  1,H n . 

Proof. We will prove this result in five cases.  

Case 1. If n = 1 (mod 5) then n = 5k + 1 where k N . See Fig. 7 for a Hamiltonian path from 1 to 5k + 1. 

 

 

 

Figure 7: Hamiltonian path connecting 1 and 5k + 1 in 
5 1 2,3kT 

 



American Scientific Research Journal for Engineering, Technology, and Sciences (ASRJETS) (2017) Volume 33, No  1, pp 255-268 

259 
 

Case 2. The Hamiltonian path connecting 1 and 7 in
7 2,3T is shown in Fig. 8. If n = 2 (mod 5), then we can 

write n = 5k + 2 where .k N  For any Toeplitz graph 
5 2 2,3kT 

 for 2k    joining the path of Fig. 8 from 1 

to 7 with the path of Fig. 7 from 7 to 5k + 2 we get the Hamiltonian path connecting 1 and 5k + 2. 

 

 

 

Figure 8: Hamiltonian path between 1 and 7 in 
7 2,3T  

Case 3. The Hamiltonian path connecting 1 and 13 in Toeplitz graph 
13 2,3T , is shown in Fig. 9.  

If n = 3 (mod 5), then we can write n = 5k+3 for any 2.k   The Hamiltonian path joining vertices 1 and 5k + 3 

in any Toeplitz graph 
5 3 2,3kT 

 for 3k   is obtained by joining the path of Fig. 9 with the path of Fig 7. 

 

 

 

Figure 9: Hamiltonian path connecting 1 and 13 in 
13 2,3T  

Case 4. If n = 4 (mod 5), then n = 5k + 4 for .k N  In the Toeplitz graph 
9 2,3T  the Hamiltonian path 

connecting 1 and 9 is shown in Fig. 10. The Hamiltonian path connecting 1 and 5k + 4 for any 2k    in the 

Toeplitz graphs 
5 4 2,3kT 

 is obtained by joining the path of Fig. 10 with the path of Fig. 7. 

 

 

 

Figure 10: Hamiltonian path connecting 1 and 9 in 
9 2,3T  

Case 5. If n = 0 (mod 5). The Hamiltonian path connecting 1 and 10 in Toeplitz graph 
10 2,3T  is shown in Fig. 



American Scientific Research Journal for Engineering, Technology, and Sciences (ASRJETS) (2017) Volume 33, No  1, pp 255-268 

260 
 

11 while the Hamiltonian path connecting 1 and 5k for 3k   in the Toeplitz graphs 
5 2,3kT   is obtained by 

joining paths of Fig. 11 and Fig. 7. 

Corollary 2.6. In Toeplitz graphs 2,3nT , the Hamiltonian path  ,H l m  exists for  5m l   and  7m l  . 

 

 

 

Figure 11: Hamiltonian path connecting 1 and 10 in 
10 2,3T  

Corollary 2.7.  The Toeplitz graph 2,3nT  for n ≥ 9 and 11n  has a path with ends 1 and n that contains all 

vertices of the graph except vertices 2 and 3. 

Proof. The required path is “1, 4, H[4, n], n”. 

Lemma 2.8. The Toeplitz graphs 2,3nT   for all n ≥ 7 has a paths  ' 1, ,2P n  and  ' 1, , 1P n n  . 

Proof. The required paths for 
7 2,3T  and 

10 2,3T  are shown in Fig. 12. The required path for all other n is 

obtained by first connecting 1 with 3 and then connecting 3 with n using the Hamiltonian path of Lemma 2.5. 

Due to symmetry of Toeplitz graph there is a path with ends 1 and n that contains all vertices except n − 1. 

 

Figure 12: Path connecting 1 and n except 2 

Corollary 2.9. In 2,3nT  the path  ' , ,P l m k  exists for m − l ≥ 6. 

Lemma 2.10. In 2,3nT  for n ≥ 6 and 7n   7 the Hamiltonian paths  2 1,nH n  and  1

1 1,nH n  exists. 

Proof. In 
6 2,3T  the required Hamiltonian path is “ 2,5,3,1,4,6 ”. The path “ 2,5,7,4,1,3,6,8 ” is the required 

Hamiltonian path in 
8 2,3T . The required Hamiltonian path in 

9 2,3T  is “ 2,4,1,3,6,8,5,7,9 ”. In  2,3nT  for 

9n   the required path is “  2,4,1,3,P' 3, ,4 ,n n ”. 

Lemma 2.11. In 2,3,nT t , n ≥ 20 and 4 ≤ t ≤ n − 11, the Hamiltonian path  1 1,xH n  exists for all 2 x n  . 



American Scientific Research Journal for Engineering, Technology, and Sciences (ASRJETS) (2017) Volume 33, No  1, pp 255-268 

261 
 

Proof. The Hamiltonian paths between vertex 1 with all other vertices except 3n   4 7t n    are shown in 

Table 1. 

Table 1: Hamiltonian Path between 1 and other vertices. 

End Vertices Hamiltonian Path 

1 – 2, (n ≥ 6) 1, P [1, 2, n], 2. 

1 – 3, (n ≥ 10) 1, 4, 2, 5, P [5, 6, n], 6, 3. 

1 – 4, (n ≥ 10) 1, 3, 6, P [5, 6, n], 5, 2, 4. 

1 – 5, (n ≥ 11) 1, 3, 6, P [6, 7, n], 7, 4, 2, 5. 

1 – x, (n ≥ 11) 

6 ≤ x ≤ n − 5 

1,  ' 1, 1,P x x  , x + 1,  P [x, x + 1, n], x. 

1  –  (n − 4), 

(n ≥ 14) 

1, H[1, n − 5], n − 5, P [n − 5, n − 4, n], n − 4. 

1  –  (n − 2), 

(n ≥ 13) 

1, H[1, n − 4], n − 4, n − 1, n − 3, n, n − 2. 

1  –  (n − 1), 

(n ≥ 13) 

1, H[1, n − 4], n − 4, n − 2, n, n − 3, n − 1. 

1 – n,(n ≥ 9) 1, H[1, n], n. 

Hamiltonian Path Between 1 and (n − 3) in 2,3,nT t , for different values of t  is shown in Table 2. 

Table 2: Hamiltonian Path between 1 and n − 3. 

Condition   on   t Hamiltonian Path 

t = 4,(n ≥ 14) 1, H[1, n − 5], n − 5, n − 1, n − 4, n − 2, n, n − 3. 

t = 5, (n ≥ 14) 1, H[1, n − 5], n − 5, n, n − 2, n − 4, n − 1, n − 3. 

t = 6, (n ≥ 13) 1,  ' 1, 6, 7P n n  , n − 6, n, n − 2, n − 5, n − 7, n −4, n − 1, n − 3. 

t = 7, (n ≥ 14) 1, P l[1, n − 7, n − 8], n − 7, n, n − 2, n − 5, n − 8, n −6, n − 4, n − 1, n − 3. 

t = 8, (n ≥ 15) 1, P l[1, n − 8, n − 9], n − 8, n, n − 2, n − 5, n − 7, n −9, n − 6, n − 4, n − 1, n − 3. 

9 ≤ t ≤ n − 11, 

(n ≥ 20) 

1, H[1, n − t − 2], n − t − 2, P [n − t − 2, n − t − 1, n −5], n − t − 1, n − 1, n − 4, 

 n − 2, n, n − 3. This path is shown in Fig. 13. 

 

 

 

 

Figure 13: Hamiltonian path with ends 1 and 3n   in 2,3, tnT  when 4 6t n    

Lemma 2.12. In 2,3,nT t , n ≥ 18 and 4 ≤ t ≤ n − 10, the Hamiltonian path  1 1,xH n  exists for all 1 ≤ x ≤ n  



American Scientific Research Journal for Engineering, Technology, and Sciences (ASRJETS) (2017) Volume 33, No  1, pp 255-268 

262 
 

2x  . 

Proof. The Hamiltonian path of 2 with 1 is proved in Lemma 2.11 and with all other vertices except 3n   is 

shown in Table 3. 

Table 3: Hamiltonian Path of 2 with other vertices. 

End Vertices Hamiltonian Path 

2 – 3, (n ≥ 9) 3, 1, 4, P [4, 5, n], 5, 2. 

2 – 4, (n ≥ 10) 2, 5, P [5, 6, n], 6, 3, 1, 4. 

2 – 5, (n ≥ 10) 2, 4, 1, 3, 6, P [5, 6, n], 5. 

2 – 6, (n ≥ 10) 2, 4, 1, 3, 5, P [5, 6, n], 6. 

2 – 7, (n ≥ 11) 2, 5, 3, 1, 4, 6, P [6, 7, n], 7. 

2 – x, (n ≥ 14) 

9 ≤ x ≤ n − 4 
2,  1

2 1, 1xH x   , x − 1, P [x − 1, x, n], x. 
 

2  –  (n − 1), 

(n ≥ 13) 
2,  5

2 1, 5nH n  , n − 5, n − 3, n, n − 2, n − 4, n − 1. 
 

2  –  (n − 2), 

(n ≥ 12) 
2,  4

2 1, 4nH n  , n − 4, n − 1, n − 3, n, n − 2. 
 

2 – n, (n ≥ 8) 2,  2 1,nH n , n. 
 

 

The Hamiltonian path of 2 with 3n    for 4 4 10t n    is shown in Table 4. 

Table 4: Hamiltonian Path of 2 with 3n   

Condition on t Hamiltonian Path 

t = 4, (n ≥ 13) 2,  5

2 1, 5nH n  , n − 5, n − 1, n − 4, n − 2, n, n − 3. 
 

t = 5, ( 13n  ) 2,  5

2 1, 5nH n  , n − 5, n, n − 2, n − 4, n − 1, n − 3. 

t = 6, ( 16n  )  2,4,1,3, 3, 6 , 6, , 2, 5, 7, 4, 1, 3P n n n n n n n n n          

t = 7, (n ≥ 17) 2, 4, 1, 3, P [3, n − 7], n − 7, n, n − 2, n − 5, n − 8, n −6, n − 4, n − 1, n − 3. 

8 ≤ t ≤ n − 10, 

(n ≥ 18) 

2,  2

2 1, 2n tH n t    , n − t − 2, P [n − t − 2, n − t −2 1, n − 5], n − t − 1, n − 1, n − 4, 
n − 2, n, n − 3.  

Lemma 2.13. In 2,3,nT t , n ≥ 20 and 4 ≤ t ≤ n − 11, the Hamiltonian path  3 1,xH n  exists for all 1 ≤ x ≤ n and 

3x  . 

Proof. The concerned Hamiltonian path of 3 with 1 and 2 are shown in Lamma's 2.11 and 2.12 respectively. 

Hamiltonian path of 3 with 4 is shown in Table 5. 

 

 



American Scientific Research Journal for Engineering, Technology, and Sciences (ASRJETS) (2017) Volume 33, No  1, pp 255-268 

263 
 

Table 5: Hamiltonian Path of 3 with 4 

Condition  on  t Hamiltonian Path 

 4,t     10n     3,1,5, 5,6, ,6,2,4.P n   

5,t    11n    3.5,2,7, 6,7, ,6,1,4.P n   

6,t     14n     3,5,2,8,6,9, 9,10, ,10,7,1,4.P n   

7,t    14n     3,1,8,6,9, 9,10, ,10,7,1,4.P n   

t = 8, n ≥ 20 3, 1, 9, 7, 15, P [15, 16, n], 16, 13, 11, 14, 12, 10, 2, 5, 8, 6, 4. 

9 ≤ t ≤ n − 7 

t  =  1 (mod 2) 

(n ≥ 16) 

 3,1, 1, 2, , 3, 2, 3, , 2,2,5,7, , t 4, t 1, t 3, ,8,6,4.t t t t P t t n t          

10 ≤ t ≤ n − 7 

t  =  0 (mod 2) 

(n ≥ 17) 

3, 1, t + 1, t − 2, t − 5, t − 7, . . . , 5, 2, t + 2, P [t + 2, t +3, n], t + 3, t, t − 3, t − 1,  

t − 4, t − 6, . . . , 8, 6, 4. 

 

The Hamiltonian path between 3 and 5 for 4 ≤ t ≤ n − 8 is shown in Table 6. 

Table 6: Hamiltonian Path of 3 with 5 

Condition  on   t Hamiltonian Path 

t = 4, (n ≥ 11) 3, 1, 4, 7, P [6, 7, n], 6, 2, 5. 

t =  0 (mod 2) 
6 ≤ t ≤ n − 7 (n ≥ 13) 

3, 1, t + 1, t − 1, t − 3, . . . , 7, 4, 6, 8, . . . , t, t + 3, P [t +2, t + 3, n], t + 2, 2, 5. 

t =  1 (mod 2)  
5 ≤ t  ≤ n − 8 (n ≥ 
13) 

3, 1, t + 1, t + 4, P [t + 3, t + 4, n], t + 3, t, t −2, . . . , 7, 4, 6, 8, . . . 

, t − 1, t + 2, 2, 5. 

The Hamiltonian paths of 3 with vertices in the set  6,7,8, ,n  except 3n    are shown in Table 7. 

Table 7: Hamiltonian Path of 3 with 5. 

End Vertices Hamiltonian Path 

3 – 6, (n ≥ 10) 3, 1, 4, 2, 5, P [5, 6, n], 6. 

3 – 7, (n ≥ 14) 3, 1, 4, 2, 5,  7

5 5,H n , 7.  

  3 8 ,  14n     3, 1, 4, 2, 5,  8

5 5,H n , 8. 

3 – 9, (n ≥ 15) 3, 1, 4, 2, 5,  9

5 5,H n , 9. 
 

3  –  10,  (n  ≥16) 3, 1, 4, 2, 5,  10

5 5,H n , 10. 
 

3 – x, (n ≥ 16) 

11 ≤ x ≤ n − 5 
3, 1, 4, 2, 5, 'P [5, x + 1, x], x + 1, P [x, x + 1, n], x. 

3 – n, (n ≥ 17) 3, 1, 4, 2, 5, H[5, n], n. 

3  –  (n  − 1), (n ≥ 13) 3, 1, 4, 2, 5, 'P [5, n − 2, n − 3], n − 2, n, n − 3, n − 1. 

3 – (n − 2), (n ≥ 17) 3, 1, 4, 2, 5, H[5, n − 4], n − 4, n − 1, n − 3, n, n − 2. 

3 – (n − 4), n ≥ 18 3, 1, 4, 2, 5, H[5, n−5], n−5, n−2, n, n−3, n−1, n−4. 



American Scientific Research Journal for Engineering, Technology, and Sciences (ASRJETS) (2017) Volume 33, No  1, pp 255-268 

264 
 

The Hamiltonian path between 3 and 3n   for 4 7t n    is given in the Table 8. 

Table 8: Hamiltonian Path between 3 and 3n   

Condition  on  t Hamiltonian Path 

t = 4, (n ≥ 18) 3, 1, 4, 2, 5, H[5, n − 5], n − 5, n − 1, n − 4, n − 2, n, n − 3 

t = 5, (n ≥ 18) 3, 1, 4, 2, 5, H[5, n − 5], n − 5, n, n − 2, n − 4, n − 1, n − 3. 

t = 6, (n ≥ 17) 3, 1, 4, 2, 5, 'P [5, n − 6, n − 7], n − 6, n, n − 2, n − 5, n −7, n − 4, n − 1, n − 3. 

t = 7, (n ≥ 18) 3, 1, 4, 2, 5, 'P [5, n − 7, n − 8], n − 7, n, n − 2, n − 5, n − 8, n − 6, n − 4, n − 1, n − 3. 

t = 8, (n ≥ 19) 3, 1, 4, 2, 5, 'P [5, n − 8, n − 9], n − 8, n, n − 2, n − 5, n −7, n − 9, n − 6, n − 4, n − 1, n − 3. 

9 ≤ t ≤ n − 11, 

(n ≥ 20) 

3, 1, 4, 2, 5, 'P [5, n − t, n − t − 1], n − t, P [n − t, n − t −1, n − 5], n − t − 1, n − 1, n − 4, 

 n − 2, n, n − 3. 

 

Lemma 2.14. In 2,3,nT t , n ≥ 24 and 4 ≤ t ≤ n − 11, the Hamiltonian path 5

xH [1, n] exists for all 1 ≤ x ≤ n 

and 5.x    

Proof. The Hamiltonian path of 5 with vertices 1, 2 and 3 is already shown. The Hamiltonian path of vertex 4 

with 5 for different values of t is given in Table 9. 

Table 9: Hamiltonian Path of Vertex 4 with vertex 5 

Values  of  t Hamiltonian Path 

t = 4, (n ≥ 11) 4, 1, 3, 7, P [6, 7, n], 6, 2, 5. 

t = 5, (n ≥ 11) 4, 2, 7, P [6, 7, n], 6, 1, 3, 5. 

t = 6, (n ≥ 14) 4, 2, 8, 6, 9, P [9, 10, n], 10, 7, 1, 3, 5. 

t = 7, (n ≥ 15) 4, 7, 10, P [10, 11, n], 11, 8, 1, 3, 6, 9, 2, 5. 

t = 8, (n ≥ 15) 4, 2, 10, P [10, 11, n], 11, 8, 6, 3, 1, 9, 7, 5. 

t = 9, (n ≥ 17) 4, 1, 3, 12, P [12, 13, n], 13, 10, P [10, 11, 6], 11, 2, 5. 

10 ≤ t ≤ n − 7 

(n ≥ 17) 
4, 2, t + 2, P [t + 2, t + 3, n], t + 3, t, P [t, t + 1, 6], t +1, 1, 3, 5. 

The Hamiltonian path of vertex 5 with vertex 6 in Toeplitz graph 2,3, tnT  for all values of 4 ≤ t ≤ n − 7 and n ≥ 14 

is given in Table 10. 

Table 10: Hamiltonian Path of Vertex 5 with vertex 6 

Conditions on t Hamiltonian Path 

t = 4, (n ≥ 11) 5, 2, 4, 1, 3, 7, P [6, 7, n], 6. 

t = 5, (n ≥ 11) 5, 3, 1, 4, 2, 7, P [6, 7, n], 6. 

t = 6, (n ≥ 12) 5, 3, 1, 7, P [7, 8, n], 8, 2, 4, 6. 

t = 7, (n ≥ 15) 5, 3, 1, 8, 11, P [10, 11, n], 10, 7, 9, 2, 4, 6. 

t = 8, (n ≥ 16) 5, 8, 11, P [11, 12, n], 12, 9, 7, 10, 2, 4, 1, 3, 6. 



American Scientific Research Journal for Engineering, Technology, and Sciences (ASRJETS) (2017) Volume 33, No  1, pp 255-268 

265 
 

 

9 ≤ t ≤ n − 7, 

(n ≥ 16) 
5, 3, 1, 4, 2, t + 2, P [t + 2, t + 3, n], t + 3, P l[6, t + 3, t + 2], 6. 

The Hamiltonian path of vertex 5 with vertex x such that 7 ≤ x ≤ n and 3x n    in Toeplitz graph 

2,3,nT t   for 4 ≤ t ≤ n − 7 and n ≥ 25 is “5, 2, 4, 1, 3, 6,  6 6,xH n ,, x  ” 

Main  Result 

Theorem 3.1. The Toeplitz graph 2,3, tnT   is Hamiltonian connected for all n ≥ 28 and 
8

4
2

n
t


   

Proof. For every  , 2,3, tnx y V T , and 6 5x y n     the Hamiltonian path for different conditions on 

,y x  for 4 7t n    and for 17n   is shown in Table 11. 

Table 11: Hamiltonian Path between x and y when 6 5x y n     

Conditions on x and y Hamiltonian Path 

y − x ≥ 5 and n ≥ 16 x, P [x − 1, x, 1], x − 1, P [x − 1, y + 1], y + 1, P [y, y +1, n], y. 

y − x = 1 and n ≥ 12 x, P [x − 1, x, 1], x − 1, y + 1, P [y, y + 1, n], y. 

y − x = 2 and n ≥ 13 x, P [x − 1, x, 1], x − 1, x + 1, y + 1, P [y, y + 1, n], y. 

y − x = 3 and n ≥ 14 x, P [x, x + 1, 1], x + 1, y + 1, x + 2, y + 2, P [y + 2, y +3, n], y + 3, y. 

y − x = 4 and n ≥ 16 x, P [x − 1, x, 1], x − 1, x + 2, y + 1, P [y + 1, y + 2, n], y +2, x + 3, x + 1, y. 

The Hamiltonian path of vertex 4 with vertex 6 in Toeplitz graph 2,3,nT t  for all values of 4 ≤ t ≤ n − 7 is given in 

Table 12. 

Table 12: Hamiltonian Path of Vertex 4 with vertex 6 

Values of  t Hamiltonian Path 

t = 4, (n ≥ 12) 4, 1, 3, 7, P [7, 8, n], 8, 5, 2, 6. 

t = 5, (n ≥ 11) 4, 1, 3, 5, 2, 7, P [6, 7, n], 6. 

t = 6, (n ≥ 11) 4, 2, 5, 3, 1, 7, P [6, 7, n], 6. 

t = 7, (n ≥ 12) 4, 2, 5, 7, P [7, 8, n], 8, 1, 3, 6. 

t = 8, (n ≥ 16) 4, 2, 5, 7,  9

7 7,H n , 9, 1, 3, 6. 
 9  ≤ t ≤ n – 7, (n ≥ 16) 4, 1, 3, 5, 2, t+2, P [t+2, t+3, n], t+3, 'P [6, t+3, t+2], 6. 

The Hamiltonian path of vertex 4 with vertex 7 in Toeplitz graph 2,3,nT t  for all values of 4 ≤ t ≤ n − 7 is given in 

Table 13. 

The Hamiltonian path of vertex 4 with vertex 8 in Toeplitz graph 2,3,nT t  for all values of 4 ≤ t ≤ n − 7 is given in 

Table 14. 



American Scientific Research Journal for Engineering, Technology, and Sciences (ASRJETS) (2017) Volume 33, No  1, pp 255-268 

266 
 

The Hamiltonian path of vertex 4 with vertex 9 in Toeplitz graph 2,3,nT t  for all values of 4 7t n    is 

given in Table 15. 

Table 13: Hamiltonian Path of Vertex 4 with vertex 7 

Values of  t Hamiltonian Path 

t = 4, (n ≥ 11) 4, 1, 3, 5, 2, 6, P [6, 7, n], 7. 

t = 5, (n ≥ 11) 4, 2, 5, 3, 1, 6, P [6, 7, n], 7. 

t = 6, (n ≥ 14) 4, 1, 3, 5, 2, 8, 6, 9, P [9, 10, n], 10, 7. 

t = 7, (n ≥ 14) 4, 2, 5, 3, 1, 8, 6, 9, P [9, 10, n], 10, 7. 

t = 0 (mod 2)  

 8 ≤ t ≤ n − 7 (n ≥ 5) 

4, 2, t+2, P [t +2, t+3, n], t+ 3, t, 2t   , . . . , 8, 6, 9, 11, . . . , t + 1, 1, 3, 5, 7. 

t = 1 (mod 2) 

9 ≤ t ≤ n − 7 (n ≥ 

17) 

4, 2, t+2, P [t+2, t+3, n], t+3, t, 2t  , t−4, . . . , 9, 6, 8, 10, . . . , t + 1, 1, 3, 5, 

7. 

 

Table 14: Hamiltonian Path of Vertex 4 with vertex 8 

Values of t Hamiltonian Path 

t = 4, (n ≥ 15) 4, 1, 3, 5, 2, 6, 9, 7, 10, P [10, 11, n], 11, 8. 

t = 5, (n ≥ 15) 4, 2, 5, 3, 1, 6, 9, 7, 10, P [10, 11, n], 11, 8. 

t = 6, (n ≥ 15) 4, 2, 5, 3, 1, 7, 10, P [9, 10, n], 9, 6, 8. 

t = 7, (n ≥ 18) 4, 1, 3, 5, 2, 9,  8

9 6,H n , 8. 

t = 8, (n ≥ 14) 4, 7, 5, 2, 10, P [9, 10, n], 9, 1, 3, 6, 8. 

t = 1 (mod 2) 4, 1, t + 1, t − 1, t − 3, . . . , 10, 7, 9, 11, . . . , t, t + 3, P [t + 2, t +3, n], t + 2, 2, 5, 3, 6,8 

9 ≤ t ≤ n – 7, (n ≥ 16)  

 t = 0 (mod 2) 4, 1, t + 1, t − 1, t − 3, . . . , 7, 10, 12, . . . , t, t + 3, P [t + 2, t +3, n], t + 2, 2, 5, 3, 6, 8. 

10 ≤ t ≤ n – 7 , (n ≥ 17)  

 

 

Table 15: Hamiltonian Path of Vertex 4 with vertex 9 

Values of t Hamiltonian Path 

t = 4, (n ≥ 15) 4, 1, 3, 5, 2, 6,  9

6 6,H n , 9. 

6 t = 5, (n ≥ 15) 4, 1, 3, 5, 2, 7,  9

7 6,H n , 9. 

7 t = 6 (n ≥ 19) 4, 1, 3, 5, 2, 8,  9

8 6,H n ], 9. 

8 7,t    ( 19n  )  4, 2, 5, 3, 1, 8,  9

8 6,H n , 9. 

t = 8, (n ≥ 15) 4, 1, 3, 6, 8, 11, P [10, 11, n], 10, 2, 5, 7, 9. 

t = 9, (n ≥ 15) 4, 1, 3, 6, 8, 10, P [10, 11, n], 11, 2, 5, 7, 9. 

t = 1 (mod 2)  

11 ≤ t ≤ n − 7 (n ≥ 

18) 

4, 7, 5, 2, t+2, P [t+2, t+3, n], t+3, t, t−2, t−4, . . . , 11, 8, 10, 12, . . . , t + 1, 1, 3, 6, 9. 

t = 0 (mod 2)  

10 ≤ t ≤ n − 7 (n ≥ 

17) 

4, 7, 5, 2, t+2, P [t+2, t+3, n], t+3, t, t−2, t−4, . . . , 8, 11, 13, 15, . . . , t + 1, 1, 3, 6, 9. 



American Scientific Research Journal for Engineering, Technology, and Sciences (ASRJETS) (2017) Volume 33, No  1, pp 255-268 

267 
 

 

The Hamiltonian path of vertex 4 with vertex 10 in Toeplitz graph 2,3,nT t  for all values of 4 7t n    is 

given in Table 16. 

Table 16: Hamiltonian Path of Vertex 4 with vertex 10 

Condition on  t Hamiltonian Path 

4 ≤ t ≤ n − 7, 8t  , (n ≥ 22) 4, 1, 3, 5, 2, t + 2,  2

10 6,tH n
, 10. 

10 t = 8, (n ≥ 20) 4, 2, 5, 3, 1, 9,  10

9 6,H n , 10. 

9 
 

The Hamiltonian path of vertex 4 with vertex x for 11 5x n    in Toeplitz graph 2,3,nT t  for all values of 

8
4

2

n
t


   and 27n   is given in Table 17. 

Table 17: Hamiltonian Path of Vertex 4 with vertex 11 5x n    

Condition on  t Hamiltonian Path 

t = 4, (n ≥ 24) 4, 1, 3, 5, 2, 6,  6 6,xH n , x. For all 7 ≤ x ≤ n. 

6 t = 5, (n ≥ 24) 4, 2, 5, 3, 1, 6,  6 6,xH n , x. For all 7 ≤ x ≤ n. 

6 t = 6, (n ≥ 24) 4, 2, 5, 3, 1, 7,  7 6,xH n , x. For all 8 ≤ x ≤ n. 

7 t = 7, (n ≥ 25) 4, 2, 5, 3, 1, 8,  8 6,xH n , x. For all 9 ≤ x ≤ n. 

8 t = 8, (n ≥ 26) 4, 1, 3, 5, 2, 10,  10 6,xH n , x. For all 11 ≤ x ≤ n. 

10 9,t     26n    4, 2, 5, 3, 1, 10,  10 6,xH n , x. For all 11 ≤ x ≤ n.  

10 ≤ t ≤ n − 7, x = t+1, (n ≥ 21) 4, 1, 3, 5, 2, t + 2,  2 6,x

th n , x. For all 11 ≤ x ≤ n − 5. 

 10 ≤ t ≤ n − 7,x /= t+1, (n ≥ 21) 4, 2, 5, 3, 1, t+1,  1 6,t

xh n
, x Hamiltonian path of Table 11, 

 

x. 
The Hamiltonian path of vertex 4 with vertex 3n  , for  

8
10

2

n
t


   and for 28n   is “ 4,1,3,5,2, 2,t    

     2, 1,6 , 1, ' 1, 1, 2 , 1, 1, , 5 , , , 2, 4, 1, 3P t t t P t n t t n t P n t n t n n t n n n n n                  ’’. 

2. Conclusion 

S. Malik and T. Zamfirescu investigated Hamiltonian properties of Toeplitz graphs in [8].  M. F. Nadeem 

Ayesha Shabbir and Tudor Zamfirescu complete the picture of  Toeplitz graphs 
1 2, , 1,3,n nT t t T t  and 

1,5, tnT   in [9]. In this paper we proved that the Toeplitz graphs 2,3, tnT  are Hamiltonian connected for 

28n   and 
8

4
2

n
t


  . It would be interesting to derive similar results for other families of 

Toeplitz graphs such as 2,5, tnT  and generalize the results for 2,s, tnT .  



American Scientific Research Journal for Engineering, Technology, and Sciences (ASRJETS) (2017) Volume 33, No  1, pp 255-268 

268 
 

References 

[1] R. Van Dal, G. Tijssen, Z. Tuza, J. A. A. Van Der Veen, Zamfirexcu, T. Zamfirescu, “Hamiltonian 

properties of Toeplitz graphs”, Discrete Mathe- matics 159, 69–81 (1996). 

[2]  R. Euler, “ Characterizing bipartite Toeplitz graphs”. Theor. Comput. Sci. 263, 47–58 (2001). 

[3] R. Euler, H. Leverge, T. Zamfirescu, “A characterization of infinite, bipartite Toeplitz graphs”. In: Tung-

Hsin, K. (ed.) Combinatorics and Graph Theory 95, Vol. 1. Academia Sinica, pp. 119–130. World 

Scientific, Sin- gapore (1995). 

[4] R. Euler, T. Zamfirescu, “ On planar Toeplitz graphs”. Graphs Comb. 29, 13111327 (2013). 

[5] C. Heuberger, “On Hamiltonian Toeplitz graphs”. Discret. Math. 245, 107– 125 (2002). 

[6] S. Malik, “Hamiltonicity in directed Toeplitz graphs of maximum (out or in) degree 4”. Util. Math. 89, 

33–68 (2012) 

[7] S. Malik, A. M. Qureshi, “Hamiltonian cycles in directed Toeplitz graphs”. Ars Comb. 109, 511– 526 

(2013). 

[8] S. Malik, T. Zamfirescu, “ Hamiltonian connectedness in directed Toeplitz graphs”. Bull. Math. Soc. Sci. 

Math. Roum. 53 (101) No. 2, 145156 (2010). 

[9] M. F. Nadeem, A. Shabbir, T. Zamfirescu, “Hamiltonian Connectedness of Toeplitz Graphs”. Springer Basel 

2015 P. Cartier et al. (eds.), Mathematics in the 21st Century, Springer Proceedings in Mathematics & 

Statistics 98, DOI 10.1007/978-3-0348-0859-08.