Hamltonian Connectedness and Toeplitz Graphs

  • Hassan Zafar National College of Business & Administration, DHA Campus, Lahore 54590, Pakistan
  • Naveed Akhter Govt. Dyal Singh College, Lahore 54590 , Pakistan
  • Muhammad Kamran Jamil Riphah Institute of Computing and Applied Sciences (RICAS) Riphah International University, Lahore 54590, Pakistan. , Pakistan
  • Faisal Nadeem Department of Mathematics, COMSATS, Institute of Information and Technology, Lahore 54590, Pakistan
Keywords: Hamiltonian graph, Hamiltonian connected, Toeplitz graph, Toeplitz matrix, Hamiltonian path.


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 , for   and  are Hamiltonian  connected.


[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.