On \(k\)-step Hamiltonian graphs (Q2927768)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: On \(k\)-step Hamiltonian graphs |
scientific article; zbMATH DE number 6365689
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | On \(k\)-step Hamiltonian graphs |
scientific article; zbMATH DE number 6365689 |
Statements
4 November 2014
0 references
Hamiltonian tour
0 references
\(k\)-step Hamiltonian tour
0 references
NP-complete
0 references
On \(k\)-step Hamiltonian graphs (English)
0 references
A simple graph is said to admit an AL(\(k\))-traversal if there exists a sequence of vertices such that the distance between two adjacent vertices in the sequence is equal to \(k\). A graph is \(k\)-step Hamiltonian if it has an AL(\(k\))-traversal and the distance between the first and last vertex in the sequence is equal to \(k\). This paper considers graphs that are \(k\)-step Hamiltonian. The authors show that all bipartite graphs are not \(k\)-step Hamiltonian for even integer \(k\). Any graph is shown to be an induced subgraph of a \(k\)-step Hamiltonian graph.
0 references
