On hamiltonian Toeplitz graphs (Q1348117)

From MaRDI portal
Revision as of 10:49, 16 February 2024 by RedirectionBot (talk | contribs) (‎Changed an Item)
scientific article
Language Label Description Also known as
English
On hamiltonian Toeplitz graphs
scientific article

    Statements

    On hamiltonian Toeplitz graphs (English)
    0 references
    0 references
    15 May 2002
    0 references
    Let \(n,m,a_1,\dots,a_m\in \mathbb{N}\), \(0<a_1<\cdots <a_m<n\) and \(V:=\{0,\dots,n-1\}\). Define \(E:=\{[i,j]\in V^2:|j-i|=a_k\) for some \(k\in\{1,\dots,m\}\}.\) Then the graph \((V,E)\) with set of vertices \(V\) and set of edges \(E\) is called an undirected Toeplitz graph with stripes \(a_1,\dots,a_m\). The author considers connectivity properties and hamiltonian properties of Toeplitz graphs. A sufficient condition for a Toeplitz graph to be connected is described and a complete characterization of connected Toeplitz graphs with two stripes is given. An infinite family of hamiltonian and of nonhamiltonian Toeplitz graphs with two stripes are described. Sufficient conditions for Toeplitz graphs with many entries to be hamiltonian are derived as well. Note that the circulant graphs are special Toeplitz graphs.
    0 references
    Toeplitz graphs
    0 references
    circulant graphs
    0 references
    Hamilton cycles
    0 references
    connectivity
    0 references
    travelling salesman problem
    0 references

    Identifiers