# The Property of Hamiltonian Connectedness in Toeplitz Graphs

Authors: Ayesha Shabbir; Muhammad Faisal Nadeem; Tudor Zamfirescu
Journal: Complexity
 (2020)

---

## Abstract

A spanning path in a graphG is called a Hamiltonian path. To determine which graphs possess such paths is an NP-complete problem. A graph G is called Hamiltonian-connected if any two vertices of G are connected by a Hamiltonian path. We consider here the family of Toeplitz graphs. About them, it is known only for n=3 that Tnp,q is Hamiltonian-connected, while some particular cases of Tnp,q,r for p=1 and q=2,3,4 have also been investigated regarding Hamiltonian connectedness. Here, we prove that the nonbipartite Toeplitz graph Tn1,q,r is Hamiltonian-connected for all 1<q<r<n and n≥5r−2.


---

## Body

## 1. Introduction

A path in a finite undirected graphG is called a Hamiltonian path if it visits each vertex of G exactly once. We call the graph G Hamiltonian-connected if for any pair of distinct vertices x and y of G, there exists a Hamiltonian path from x to y. In 1963, Ore introduced the family of Hamiltonian-connected graphs [13]. The Hamiltonian path problem, is the computational complexity problem of finding Hamiltonian paths in graphs, and related graphs are among the most famous NP-complete problems, see [14]. In this paper, we are investigating this property of Hamiltonian connectedness for some classes of Toeplitz graphs.Letn,t1,t2,…,tk∈ℕ such that 1≤t1<t2<⋯<tk<n. An undirected Toeplitz graph Tnt1,t2,…,tk is a symmetric graph with the vertex set 1,2,…,n and with an edge i,j between the vertices i and j if and only if j−i=tl for some l∈1,2,…,k. The integers t1,t2,…,tk are called entries or jumps. The adjacency matrix of any such graph is a symmetric Toeplitz matrix. Toeplitz graphs were introduced by G. Sierksma. The undirected Toeplitz graphs were first investigated by van Dal et al. [14] with respect to hamiltonicity. Heuberger [8] extended this study in 2002, while the directed case was studied in [9–11]. For results regarding different properties of Toeplitz graphs such as connectivity, bipartiteness, planarity, and colourability, see [3–8]. The well-known circulant graphs are particular cases of Toeplitz graphs. In fact, for each Toeplitz graph T, there exists a circulant graph C such that T is a spanning subgraph of C.Forn,t1,t2,…,tk∈ℕ, a circulant graph Cnt1,t2,…,tk is a regular graph of degree 2k or 2k−1 with the vertex set 0,1,2,…,n−1, in which two vertices i and j are adjacent if and only if j−i=tlmodn, for some l∈1,2,…,k. Circulant graphs are Cayley graphs on the abelian group Zn, i.e., the circulant graph Cnt1,t2,…,tk is the Cayley graph CayZn,t1,t2,…,tk. Furthermore, note that Cn1,2,…,n/2≅Kn and Cn1≅Cn (a cycle or cyclic graph on n vertices).For results regarding connectivity of the Toeplitz graph, see [14], where it is shown that the graph Tnt1,t2,…,tk has at least gcdt1,t2,…,tk components. Therefore, for gcdt1,t2,…,tk>1, the corresponding Toeplitz graph is disconnected. But, one may find a disconnected graph even for gcdt1,t2,…,tk=1, e.g., T63,5.In [11], it has been proven that Tn1,2 is Hamiltonian-connected only for n=3, while Tn1,2,s is Hamiltonian-connected for all values of n and s. The present paper is a sequel of [12], where it is proved that Tnt1,t2 is Hamiltonian-connected only for n=3. Thereafter, the case k=3 was considered and it was shown that the graphs Tn1,3,t3 and Tn1,4,t3 are Hamiltonian-connected. Here, we are presenting a more general result about Tn1,t2,t3 with 1<t2<t3<n under the assumption that t2 and t3 are not both odd because otherwise the corresponding Toeplitz graph becomes bipartite, hence not Hamiltonian-connected [12]. A Toeplitz graph becomes circulant if for each entry ti, n−ti also occurs as an entry for all i=1,2,…,k, see [1]. In this special class of Toeplitz graphs, we prove here the existence of Hamiltonian-connected graphs.The following results are needed to prove our first result.Theorem 1 (see [2]).
A connected Cayley graph on an abelian group is Hamiltonian-connected if and only if it is neither cyclic nor bipartite.Theorem 2 (see [15]).
The circulant graphCnt1,t2,…,tr is connected if and only if gcdt1,t2,…,tr,n=1.Theorem 3 (see [7]).
A connected circulant graphCnt1,t2,…,tr is bipartite if and only if t1,t2,…,tr are odd and n is even.


## 2. Main Results

We start with the following result which is a consequence of Theorem1.Theorem 4.
Ifn is an odd integer and k≥2 such that tk≤n/2 and gcdt1,…,tk,n=1, then Tnt1,…,tk,n−tk,…,n−t1 is Hamiltonian-connected.Proof.
SinceT=Tnt1,t2,…,tk,n−tk,…,n−t1≅Cnt1,t2,…,tk, under the given conditions and by Theorems 2 and 3, T is a connected noncyclic and nonbipartite Cayley graph CayZn,t1,t2,…,tk. Hence, it is Hamiltonian-connected by Theorem 1.To prove our next main results, we need the following notation and lemmas.LetT be a Toeplitz graph and p,q p<q be two vertices of T. The symbols Gp,q and G¯q,p stand for the paths p,p+1p+1,p+2⋯q−1,q and q,q−1q−1,q−2…p+1,p, respectively. By Pp,q, we mean a path from p to p+1 with the set of vertices p,p+1,p+2,…,q−2,q−1,q, and by Pq,p, we mean a path from q to q−1 with the same vertices. Note that the existence of Pp,q or Pq,p is not guaranteed. Furthermore, it is easy to observe that if T is a Toeplitz graph of order n and there exists a path v1,v2…vk−1,vk in T, then by the symmetry of Toeplitz graphs, there exists another path n+1−v1,n+1−v2…n+1−vk−1,n+1−vk in T.Lemma 1.
Ift is an even integer with n∈t+1,t+3,…,2t−3 or n≥2t−1, then Tn1,t admits a Hamiltonian path from 1 to 2.Proof.
Forn∈t+1,t+3,…,3t−3, the Toeplitz graph Tn1,t with t even admits a unique Hamiltonian path which is starting from 1, passing through the edge n−1,n, and ending at 2. We use these paths as basic paths to construct our desired path in T=Tn1,t, which are defined as follows:
Whenn=t+1,(1)P:1,t+1G¯t+1,2.
Whenn=t+i for some i∈3,5,…,t−1,(2)P′:1,t+1G¯t+1,ii,t+it+i,t+i−1t+i−1,i−1i−1,i−2i−2,t+i−2…t+3,t+2t+2,2.
Whenn=2t+i for some i∈1,3,…,t−3,(3)P″:1,t+1Gt+1,t+it+i,2t+iG¯2t+i,2t2t,tt,t−1t−1,2t−12t−1,2t−22t−2,t−2…i+2,t+i+2t+i+2,t+i+1t+i+1,i+1G¯i+1,2.
See also Figures1(a)–1(c), respectively, for the illustration of P, P′, and P″.
Now, by usingP, P′, and P″, we construct a Hamiltonian path from 1 to 2 in Tn1,t as follows.
Whenn≡2modt−1, a desired path obtained by using P is shown in Figure 2(a).
Whenn≡1+imodt−1 for some i∈3,5,…,t−1, we use P and P′ to get a suitable path shown in Figure 2(b).
Finally, whenn≡2+imodt−1≥2t+1 for some i∈1,3,5,…,t−3, we consider P and P″ to obtain a path given in Figure 2(c) as desired.Figure 1
P
,
P
′, and P″ basic paths.Figure 2
Hamiltonian path from 1 to 2 inT, when t is even. (a) n ≡ 2(mod (t − 1)). (b) n ≡ (1 + i)(mod (t − 1)); i ∈ {3, 5,…, t − 1}. (c) n ≡ (2 + i)(mod (t − 1)) ≥ 2t + 1; i ∈ {1, 3, …, t − 3}.
(a)
(b)
(c)Lemma 2.
Ift is an odd integer and n is an even integer, then Tn1,t admits a Hamiltonian path from 1 to 2.Proof.
Letn≡1+imodt−1 be an even integer for some i∈1,3,…,t−2. For i=1, consider the path shown in Figure 2(a), while for other values of i, follow the path shown in Figure 2(b).Immediate consequences of Lemmas1 and 2 are as follows.Corollary 1.
Lett be an even integer and p<q be any two vertices of T=Tn1,t. Then, paths Pp,q and Pq,p exist in T if q−p∈1,t,t+2,…,2t−4 or q−p≥2t−2.Corollary 2.
Lett be an odd integer and p<q be any two vertices of T=Tn1,t. Then, paths Pp,q and Pq,p exist in T if q−p=1 or q−p≥t is odd.Lemma 3.
Lett be an even integer and x be any vertex of T=T2t1,t. Then, there exists a Hamiltonian path from x to 2t in T.Proof.
Forx=1, the result is trivial. Paths for other values of x are listed in Table 1.Now, by using Corollary1 and Lemma 3, we prove our next lemma.Table 1
Hamiltonian paths fromx to 2t in T2t1,t when t is even.
Conditions
Paths
1
≠
x
<
t is odd
G
x
,
t
+
1
t
+
1,1
1,2
2
,
t
+
2
t
+
2
,
t
+
3
t
+
3,3
3,4
…
x
−
2
,
x
−
1
x
−
1
,
t
+
x
−
1
G
t
+
x
−
1,2
t
x
>
t is odd
G
¯
x
,
t
+
1
t
+
1,1
G
1
,
x
+
1
−
t
x
+
1
−
t
,
x
+
1
x
+
1
,
x
+
2
x
+
2
,
x
+
2
−
t
x
+
2
−
t
,
x
+
3
−
t
…
2
t
−
1
,
t
−
1
t
−
1
,
t
t
,
2
t
x
≤
t is even
G
¯
x
,
1
1
,
t
+
1
G
t
+
1
,
t
+
x
+
1
t
+
x
+
1
,
x
+
1
x
+
1
,
x
+
2
x
+
2
,
t
+
x
+
2
t
+
x
+
2
,
t
+
x
+
3
…
2
t
−
1
,
t
−
1
t
−
1
,
t
t
,
2
t
t
,
2
t
x
>
t is even
x
,
x
−
t
x
−
t
,
x
−
1
−
t
x
−
1
−
t
,
x
−
1
x
−
1
,
x
−
2
…
t
+
2,2
2,1
1
,
t
+
1
G
¯
t
+
1
,
x
+
1
−
t
x
+
1
−
t
,
x
+
1
G
x
+
1,2
tLemma 4.
Letx<y be any two vertices of Tn1,t, where t is an even integer and n≥5t−2. Then, Tn1,t admits a Hamiltonian path from x to y, except from 2 to t+1 (by symmetry, another one from n−t to n−1).Proof.
LetT=Tn1,t be a Toeplitz graph with t even and n≥5t−2. Because of symmetry of Toeplitz graphs, it suffices to show that T admits a Hamiltonian path from any vertex x∈1,2,…,n/2 to each vertex y∈2,3,…,n x<y of T. Take x<y, any two vertices of T, other than the pair 2,t+1 of vertices. We split our proof into two cases.Case 1.
y
=
x
+
1.
Letx∈1,2,…,t, then by Corollary 1, we have paths Pt,n and Pt+2,n in T. By joining Pt,n and Pt+2,n to the remaining subgraph of T, we obtain desired Hamiltonian paths G¯x,11,t+1Pt,nG¯t,x+1 and G¯x,33,t+3Pt+2,nt+2,22,11,x+1 in T, respectively, for x≤t−1 and x=t. For illustration, see Figures 3(a) and 3(b), respectively.
Finally, to obtain Hamiltonian paths for remaining values ofx, we assume a≤x≤b, where a=t+1+it−2 and b=t+i+1t−2 are integers for some i≥0 such that b≤n/2. By applying Corollary 1 to T, we get Pa,1 and Pb+1,n in T and construct a desired path G¯x,aPa,1a−1,b+2Pb+1,nG¯b+1,x+1 from x to x+1 in T. See also Figure 3(c).Figure 3
Hamiltonian path fromx to x+1 in T when x≤n/2. (a) x ≤ t − 1. (b) x = t. (c) y = x + 1 for x > t.
(a)
(b)
(c)Case 2.
y
≠
x
+
1.
Here, we partition the vertex set ofT into 5 subsets of vertices, according to Figure 4, and consider the following two subcases.Figure 4
Five subsets of vertices.Case 3.
x
,
y
∈
A
∪
B
∪
C
.
Corollary1 guarantees the existence of Pv,n for any vertex v<n−2t+3 in T. Here, by using it, we are getting Hamiltonian paths from x to y in T.
Whenx=1, we consider the path G1,y−1Py−1,n from 1 to any vertex y in T.
Ifx≠1, then possible Hamiltonian paths for different values of x and y are listed in Tables 2–4.Table 2
Hamiltonian paths from1≠x to y in T when t is even.
x
,
y
∈
A
Conditions
Paths
y is even
G
¯
x
,
1
1
,
t
+
1
G
t
+
1
,
t
+
x
t
+
x
,
2
t
+
x
P
2
t
+
x
−
1
,
n
G
¯
2
t
+
x
−
1,2
t
2
t
,
t
t
,
t
−
1
t
−
1,2
t
−
1
2
t
−
1,2
t
−
2
2
t
−
2
,
t
−
2
…
t
+
x
+
2
,
t
+
x
+
1
t
+
x
+
1
,
x
+
1
G
x
+
1
,
y
x is even and y is odd
G
¯
x
,
1
1
,
t
+
1
G
t
+
1
,
t
+
x
+
1
t
+
x
+
1
,
x
+
1
x
+
1
,
x
+
2
x
+
2
,
t
+
x
+
2
…
y
−
2
,
y
−
1
y
−
1
,
t
+
y
−
1
G
t
+
y
−
1,2
t
−
1
P
2
t
−
1
,
n
2
t
,
t
G
¯
t
,
y
Both are odd
G
¯
x
,
1
1
,
t
+
1
G
t
+
1
,
y
+
1
y
+
1
,
t
+
y
+
1
G
t
+
y
+
1,2
t
+
2
2
t
+
2
,
t
+
2
t
+
2
,
t
+
3
t
+
3,2
t
+
3
…
t
+
x
−
1
,
t
+
x
t
+
x
,
2
t
+
x
G
¯
2
t
+
x
,
2
t
+
y
−
1
P
2
t
+
y
−
1
,
n
2
t
+
y
,
t
+
y
G
¯
t
+
y
,
t
+
x
+
1
t
+
x
+
1
,
x
+
1
G
x
+
1
,
yTable 3
Hamiltonian paths from1≠x to y in T when t is even.
1
≠
x
∈
A and y∈B∪C
Conditions
Paths
y
=
t
G
¯
x
,
1
1
,
t
+
1
G
t
+
1
,
t
+
x
P
t
+
x
,
n
t
+
x
+
1
,
x
+
1 Gx+1,t
x is odd and y=t+i; i∈2,4,…,x−1
G
¯
x
,
i
−
1
i
−
1
,
t
+
i
−
1
t
+
i
−
1
,
t
+
i
−
2 t+i−2,i−2i−2,i−3…2,1 1,t+1G¯t+1,x+1x+1,t+x+1Pt+x,nG¯t+x,y
x is odd and y=t+i; i∈1,3,…,x−2
G
x
,
t
+
1
t
+
1,1
1,2
2
,
t
+
2
t
+
2
,
t
+
3 t+3,3…i−2,i−1i−1,t+i−1 t+i−1,2t+i−1P2t+i−2,nG¯2t+i−2,t+x−1 t+x−1,x−1x−1,x−2 x−2,t+x−2t+x−2,t+x−3… y+2,y+1y+1,i+1i+1,ii,y
x is odd and y≥t+x
G
x
,
t
+
1
t
+
1,1
1,2
2
,
t
+
2
t
+
2
,
t
+
3 t+3,3…x−2,x−1x−1,t+x−1 Gt+x−1,y−1Py−1,n
x is even and y=t+1
G
¯
x
,
3
3,3
+
t
G
t
+
3
,
t
+
x
+
1
t
+
x
+
1
,
x
+
1 x+1,x+2x+2,t+x+2…t−1,t t,2t2t,2t+1P2t+1,n2t+2,t+2 t+2,22,11,t+1
x is even and y=t+i; i∈3,5,…,t−1 such that i<x+1
G
¯
x
,
1
1,1
+
t
G
t
+
1
,
t
+
i
−
1
t
+
i
−
1,2
t
+
i
−
1 P2t+i−2,nG¯2t+i−1,2t2t,tt,t−1t−1,2t−1 …t+x+3,t+x+2t+x+2,x+2 x+2,x+1x+1,t+x+1G¯t+x+1,y
x is even and y=t+x+1
G
¯
x
,
1
1
,
t
+
1
G
t
+
1
,
t
+
x
t
+
x
,
2
t
+
x
P
2
t
+
x
−
1
,
n G¯2t+x−1,2t2t,tt,t−1t−1,2t−1… t+x+3,t+x+2t+x+2,x+2 x+2,x+1x+1,y
x is even and y=t+i; i∈3,5,…,t−1 such that i>x+1
G
¯
x
,
1
1
,
t
+
1
G
t
+
1
,
t
+
x
+
1
t
+
x
+
1
,
x
+
1 x+1,x+2x+2,t+x+2…i−2,i−1 i−1,t+i−1t+i−1,2t+i−1P2t+i−2,n G¯2t+i−2,2t2t,t t,t−1t−1,2t−1…i+1,ii,y
x is even and y=t+i; i∈2,4,…,t such that i≤x
G
¯
x
,
i
−
1
i
−
1
,
t
+
i
−
1
t
+
i
−
1
,
t
+
i
−
2 t+i−2,i−2…t+2,22,11,t+1 G¯t+1,x+1x+1,t+x+1Pt+x,nG¯t+x,y
x is even and y=t+i; i∈2,4,…,t such that i>x
x
,
x
−
1
x
−
1
,
t
+
x
−
1
t
+
x
−
1
,
t
+
x
−
2 t+x−2,x−2…t+2,22,11,t+1 G¯t+1,i−1i−1,t+i−1t+i−1,t+i−2 t+i−2,i−2…x+2,x+1x+1,t+x+1 t+x+1,t+xt+x,2t+xP2t+x−1,nG¯2t+x−1,y
x is even and y≥2t+1
G
¯
x
,
1
1,1
+
t
G
t
+
1
,
t
+
x
+
1
t
+
x
+
1
,
x
+
1 x+1,x+2x+2,t+x+2…t−1,tt,2tG2t,y−1Py−1,yTable 4
Hamiltonian paths from1≠x to y in T when t is even.
x
,
y
∈
B
∪
C
Conditions
Paths
x
∈
t
+
1
,
t
+
3
,
…
,
2
t
−
3 and y=t+i; i∈2,4,…,t−2
G
¯
x
,
t
+
1
t
+
1,1
G
1
,
t
t
,
2
t
G
2
t
,
t
+
x
+
1 t+x+1,x+1x+1,x+2 x+2,t+x+2…y−2,y−1 y−1,t+y−1Gt+y−1,3t−2P3t−2,n 3t−1,2t−1G¯2t−1,y
x
∈
t
+
1
,
t
+
3
,
…
,
2
t
−
3 and y=t+i; i∈1,3,…,t−1
G
¯
x
,
t
+
1
t
+
1,1
G
1
,
i
+
1
i
+
1
,
t
+
i
+
1 t+i+1,t+i+2t+i+2,i+2 …t−1,tt,2tG2t,t+xPt+x+1,n t+x+1,x+1Gx+1,y
x
∈
t
+
1
,
t
+
3
,
…
,
2
t
−
3 and y=2t
G
¯
x
,
t
+
1
t
+
1,1
G
1
,
i
+
1
i
+
1
,
t
+
i
+
1 t+i+1,t+i+2t+i+2,i+2… t−2,2t−22t−2,3t−2G¯3t−2,2t+1 2t+1,3t+1P3t,n3t,3t−1 3t−1,2t−12t−1,t−1t−1,t t,2t=y
x
∈
t
+
1
,
t
+
3
,
…
,
2
t
−
3 and y>2t
G
¯
x
,
t
+
1
t
+
1,1
G
1
,
i
+
1
i
+
1
,
t
+
i
+
1 t+i+1,t+i+2t+i+2,i+2 …t−1,tt,2tG2t,y−1Py−1,n
x
∈
t
,
t
+
2
,
…
,
2
t
−
4
∪
C
P
x
+
1,1
G
x
+
1
,
y
−
1
P
y
−
1
,
nCase 4.
x
∈
A
∪
B
∪
C and y∈B′∪A′.
The case whenx∈C and y∈B′∪A′ is symmetric to the case when x∈A∪B and y∈C. Hence, we remain only with the case when x∈A∪B and y∈B′∪A′. Here, by Lemma 3, we have a Hamiltonian path in T2t1,t from any x∈A∪B to 2t. By symmetry, another Hamiltonian path exists from y∈B′∪A′ to n−2t+1, of vertex set n−2t+1,n−2t+2,…,n. By joining 2t to n−2t+1 by the paths G2t,n−2t+1, we get a Hamiltonian path from x to y in T.
This completes the proof.Now, by using the factTn1,t,s≅Tn1,t∪Tn1,s and Lemma 4, we prove our next main results.Theorem 5.
Ift is an even integer, then the Toeplitz graph Tn1,t,s is hamiltonian-connected for all n≥5t−2.Proof.
LetT=Tn1,t,s be a Toeplitz graph with t even and n≥5t−2. Then, because of Lemma 4, we only have to establish the existence of a Hamiltonian path from 2 to t+1. For this, we use the entry s along with other two entries 1 and t.
There are five cases to consider. In first four cases, we usePv,n to construct desired paths which exist for any vertex v≤n−2t+2 of T due to Corollary 1.(i)
Fors=t+1, considered path is(4)2,11,s+1=t+2Pt+2,nt+3,3G3,t+1.(ii)
Whens=t+i;for somei∈3,5,…,t−1, a possible path is(5)2,11,s+1=t+i+1Gt+i+1,2t+1P2t+1,n2t+2,t+2t+2,t+3t+3,33,44,t+4…t+i−1,t+it+i,iGi,t+1.(iii)
s=t+i;for somei∈2,4,…,t−2; in this case, constructed path is(6)G2,i+2i+2,t+i+2t+i+2,t+i+3t+i+3,i+3…t−1,tt,2t2t,2t+1P2t+1,n2t+2,t+2Gt+2,t+i+1t+i+1,i+11,t+1.(iv)
s∈2t,2t+1,…,n−2t+2; a desired Hamiltonian path is(7)2,11,s+1Ps,nG¯s,2t2t,tt,t−1t−1,2t−1…t+4,44,33,t+3Gt+3,t+1.(v)
s∈n−2t+3,n−2t+4,…,n−1: here, first, by using Lemma 3, we construct a path Qn−2t+1,s+1 in Tn1,t from s+1 to n−2t+1, of vertex set n−2t+1,n−2t+2,…,n. Then, by joining this path to the remaining subgraph of T, we get a Hamiltonian path(8)2,11,s+1Qn−2t+1,s+1G¯n−2t+1,2t2t,tt,t−1t−1,2t−1…t+4,44,33,t+3Gt+3,t+1,from 2 to t+1. This concludes the proof.Theorem 6.
Ift is odd and s is even, then the Toeplitz graph Tn1,t,s is Hamiltonian-connected for all n≥5s−2.Proof.
Again by virtue of Lemma4, for s even and n≥5s−2, we only need to prove the existence of a Hamiltonian path starting from 2 and ending at s+1. Here, we consider the following four cases:(i)
s=t+1; by Corollary 1, we have Pt+2,n in Tn1,s, which helps us to get a desired path:(9)2,11,t+1Gt+1,33,t+3Pt+2,n.(ii)
s=t+3; again by applying Corollary 1 to Tn1,s, we get P2t+1,n to construct a Hamiltonian path:(10)2,11,t+1G¯t+1,33,t+3t+3,t+2t+2,2t+2P2t+1,nG¯2t+1,t+4.(iii)
s∈t+5,t+7,…,2t; here,(11)2,11,t+1G¯t+1,33,t+3t+3,t+2t+2,2t+2G2t+2,2t+42t+4,t+4t+4,t+5t+5,2t+5…s−1,ss,s+tGs+t,3tP3t,n3t+1,2t+1G¯2t+1,s+1,is a desired path, which is constructed by usingP3t,n, obtained by applying Corollaries 1 and 2 to Tn1,s.(iv)
s≥2t; in this case, we use Corollaries 1 and 2 to obtain Ps+2,n in Tn1,s and Ps+2,t+2 in Tn1,t, respectively, which enables us to obtain a Hamiltonian path(12)2,11,t+1G¯t+1,33,s+3Ps+2,nPs+2,t+2,from 2 to s+1 in T. This completes the proof.


## 3. Conclusion

We proved here the existence of a numberN such that for n≥N, every nonbipartite Toeplitz graph Tn1,t,s is Hamiltonian-connected. Also, the family of Toeplitz graphs, which are also circulant, contains Hamiltonian-connected graphs.



---

*Source: 5608720-2020-03-12.xml*