Hamiltonicity in directed Toeplitz graphs Tn⟨1, 3, 6; t⟩
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
Full Text:
PDFDOI: http://dx.doi.org/10.5614/ejgta.2025.13.1.10
References
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.
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.
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.
S. Akbari, S. H. Ghorban, S. Malik, and S. Qajar, Conditions for regularity and for 2-connectivity of Toeplitz graphs, Util. Math., 110 (2019), 305–314.
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.
S. Bau, A generalization of the concept of Toeplitz graphs, Mong. Math. J., 15 (2011), 54–61.
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.
F. Boesch and R. Tindell, Circulants and their connectivities, J. Graph Theory, 8 (1984), 487–499.
Z.R. Bogdanowicz, Hyper-hamiltonian circulants, Electron. J. Graph Theory Appl., 9(1) (2021), 185–193.
R.E. Burkard and W. Sandholzer, Efficiently solvable special cases of bottleneck travelling salesman problems, Discrete Appl. Math., 32 (1991), 61–67.
E.A. van Doorn, Connectivity of circulant digraphs, J. Graph Theory, 10 (1986), 9–14.
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.
R. Euler, Coloring infinite, planar Toeplitz graphs, Tech. Report, LIBr, 1998.
R. Euler, Characterizing bipartite Toeplitz graphs, Theor. Comput. Sci., 263 (2001), 47–58.
R. Euler, Coloring planar Toeplitz graphs and the stable set polytope, Discrete Math., 276 (2004), 183–200.
R. Euler and T. Zamfirescu, On planar Toeplitz graphs, Graphs Comb., 29 (2013), 1311–1327.
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.
C. Heuberger, On hamiltonian Toeplitz graphs, Discrete Math., 245 (2002), 107–125.
S.H. Ghorban, Toeplitz graph decomposition, Trans. Comb., 1(4) (2012), 35–41.
A. Ilic and M. Basic, On the chromatic number of integral circulant graphs, Comput. Math. Appl., 60(1) (2010), 144–150.
M. Klin, V. Liskovets, and R. Poschel, Analytical enumeration of circulant graphs with prime-squared number of vertices, Sem. Lotharing Combin., 36 (1996), 1–36.
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.
M. Muzychuk, A solution of the isomorphism problem for circulant graphs, Proc. London Math. Soc., 88(1) (2004), 1–41.
S. Malik, Hamiltonicity in directed Toeplitz graphs of maximum (out or in) degree 4, Util. Math., 89 (2012), 33–68.
S. Malik, Hamiltonian cycles in directed Toeplitz graphs-part 2, Ars Comb., 116 (2014), 303-319.
S. Malik, Hamiltonian cycles in directed Toeplitz graphs Tn⟨1, 2; t1 ≤ 5, t2⟩, Util. Math., 99 (2016), 3–17.
S. Malik, Hamiltonicity in directed Toeplitz graphs Tn⟨1, 2, t1, t2⟩, Australas. J. Combin., 78(3) (2020), 434–449.
S. Malik, Corrigendum and extension to ’Hamiltonicity in directed Toeplitz graphs Tn⟨1, 2, t1, t2⟩’, Australas. J. Combin., 83(1) (2022), 173–175.
S. Malik, Hamiltonicity in directed Toeplitz graphs Tn⟨1, 3, 4; t⟩, Bull. Math. Soc. Sci. Math. Roumanie., 64(112)(4) (2021), 317–327.
S. Malik, Hamiltonicity in directed Toeplitz graphs with s1 = 1 and s3 = 4, Comput. Math. Methods., 2023, Article ID 3676487, 11 pages.
S. Malik, Hamiltonicity in directed Toeplitz graphs Tn⟨1, 3; 1, t⟩, Bull. Math. Soc. Sci. Math. Roumanie., 66(114)(3) (2023), 307–318.
S. Malik and A.M. Qureshi, Hamiltonian cycles in directed Toeplitz graphs, Ars Comb., 109 (2013), 511–526.
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.
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.
S. Malik and T. Zamfirescu, Hamiltonian connectedness in directed Toeplitz graphs, Bull. Math. Soc. Sci. Math. Roumanie., 53(101) (2010), 145–156.
M.F. Nadeem, A. Shabbir, and T. Zamfirescu, Hamiltonian connectedness of Toeplitz graphs, Springer Proc. Math. Stat., 98 (2015), 135–149.
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.
S. Nicoloso and U. Pietropaoli, On the chromatic number of Toeplitz graphs, Discrete Appl. Math., 164(1) (2014), 286–296.
I. Reiter and J. Zhou, Perfect matching transitivity of circulant graphs, Electron. J. Graph Theory Appl., 8(2) (2020), 301–311.
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.
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.
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.
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.
Refbacks
- There are currently no refbacks.
ISSN: 2338-2287
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.