On hamiltonian Toeplitz graphs (Q1348117): Difference between revisions
From MaRDI portal
Removed claim: reviewed by (P1447): Item:Q582576 |
Set profile property. |
||
(One intermediate revision by one other user not shown) | |||
Property / reviewed by | |||
Property / reviewed by: Stanlislav Jendroľ / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Latest revision as of 03:01, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On hamiltonian Toeplitz graphs |
scientific article |
Statements
On hamiltonian Toeplitz graphs (English)
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