Hamiltonian properties of Toeplitz graphs

DOI10.1016/0012-365X(95)00111-9MaRDI QIDQ1126180zbMATH OpenFDO

Authors René van Dal, Zsolt Tuza, Jack A. A. van der Veen, Gert A. Tijssen, Christina Maria Zamfirescu, Tudor Zamfirescu

Publication date 9 June 1997

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365X(95)00111-9

zbMATH Keywords

adjacency matrixHamiltonianHamiltonicityToeplitz graphtraceability

Mathematics Subject Classification ID

Paths and cycles (05C38) Eulerian and Hamiltonian graphs (05C45) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)

Review text

A Toeplitz graph is an undirected graph that has an adjacency matrix in which all of the entries are the same in any diagonal parallel to the main diagonal. The Toeplitz graph \(T_n(t_1,t_2,\dots,t_k)\) has adjacency matrix with \(k\) nonzero diagonals that contain the \(k\) rows \(0<t_1<t_2<\cdots<t_k\leq n\). Hamiltonian properties (Hamiltonicity, traceability) of these graphs are investigated. For example it is shown that the Toeplitz graph \(T_n(1,t_2,\dots,t_k)\) is Hamiltonian if and only if either \(n,t_2,\dots,t_k\) are not all of the same parity or they all are even and \(t_2\leq n/2\).

Recommendations

• On hamiltonian Toeplitz graphs
• Hamiltonicity in directed Toeplitz graphs T_n 1, 2; t₁, t₂
• Hamiltonian cycles in directed Toeplitz graphs T_n 1, 2; t₁ 5, t₂
• Hamiltonian cycles in directed Toeplitz graphs

Cites work

• Algebraic methods for Toeplitz-like matrices and operators
• Circulants and their connectivities
• Connectivity of circulant digraphs
• Efficiently solvable special cases of bottleneck travelling salesman problems
• Halin graphs and the travelling salesman problem
• scientific article; zbMATH DE number 3650737 (Why is no real title available?)
• scientific article; zbMATH DE number 3775748 (Why is no real title available?)
• Minimizing Wallpaper Waste, Part 1: A Class of Traveling Salesman Problems
• Order-Picking in a Rectangular Warehouse: A Solvable Case of the Traveling Salesman Problem
• The traveling salesman problem in graphs with 3-edge cutsets

Cited in

(35)

• On hamiltonian Toeplitz graphs
• Coloring planar Toeplitz graphs and the stable set polytope.
• A hierarchical structure for the sharp constants of discrete Sobolev inequalities on a weighted complete graph
• The maximum travelling salesman problem on symmetric Demidenko matrices
• Structural properties of Toeplitz graphs
• The property of Hamiltonian connectedness in Toeplitz graphs
• Counting independent sets in Riordan graphs
• Riordan graphs I: structural properties
• Encoding labelled \(p\)-Riordan graphs by words and pattern-avoiding permutations
• Hamiltonicity in directed Toeplitz graphs of maximum (out or in) degree 4
• Coloring Toeplitz graphs
• Two types of discrete Sobolev inequalities on a weighted Toeplitz graph
• On super edge-antimagic total labeling of Toeplitz graphs
• Hamiltonian Connectedness of Toeplitz Graphs
• scientific article; zbMATH DE number 5787327 (Why is no real title available?)
• On planar Toeplitz graphs
• On the chromatic number of Toeplitz graphs
• Exponents of primitive directed Toeplitz graphs
• Hamiltonicity in directed Toeplitz graphs T_n 1, 2; t₁, t₂
• Conditions for regularity and for 2-connectivity of Toeplitz graphs
• Connectedness of finite distance graphs
• Hamiltonian cycles in directed Toeplitz graphs
• Hamiltonian cycles in directed Toeplitz graphs T_n 1, 2; t₁ 5, t₂
• Characterizing bipartite Toeplitz graphs
• Decomposition of kth Order Slant Toeplitz Operators
• Commutativity and compactness of kth order slant Toeplitz operators
• Hamiltonicity in directed Toeplitz graphs having increasing edges of length 1, 3 and 7
• Hamiltonicity in directed Toeplitz graphs with s₁=1 and s₂=3
• A graph theoretical approach to optimizing minimum Italian domination sets
• Hamiltonicity in directed Toeplitz graphs T_n1, 3, 5; t
• Hamiltonicity in directed Toeplitz graphs T_n(1, 3; 1, t)
• Hamiltonicity in directed Toeplitz graphs T_n 1, 3, 6; t
• On metric dimension of symmetrical planer pyramid related graphs
• Structural properties of symmetric Toeplitz and Hankel matrices
• An intermediate value theorem for the decycling numbers of Toeplitz graphs

This page was built for publication: Hamiltonian properties of Toeplitz graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1126180)