Construction of Hamiltonian cycles in layered cubic planar graphs (Q1606028)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Construction of Hamiltonian cycles in layered cubic planar graphs |
scientific article |
Statements
Construction of Hamiltonian cycles in layered cubic planar graphs (English)
0 references
29 July 2002
0 references
An \(n\)-layer cubic planar graph, \(G = P(k_1,k_2,\dots,k_n)\) (\(k_1\geq 2\) and \(k_i\geq 1\) for \(i>1\)), consists of a sequence of \(n+1\) cycles, \(C_0,C_1,\dots,C_n\), such that each pair of successive cycles, \(C_i,C_{i+1}\), is joined by a matching. The matchings are constructed inductively as follows: \(k_1\) parallel (non-crossing) edges join cycles \(C_0\) and \(C_1\), creating \(k_1\) faces; \(k_i\) edges are added incident to each face created by the matching that joins \(C_{i-2}\) to \(C_{i-1}\) for each \(i>1\). The cycles \(C_i\) can be realized as a sequence of concentric circles, with \(C_0\) as the innermost circle, and the matching edges can be realized as segments of lines radiating from the center. In this paper it is proved that each layered cubic planar graph is Hamiltonian and its Hamiltonian cycle can be constructed in \(O(|V|)\) steps, where \(V=V(G)\) is the set of vertices of \(G\).
0 references
Hamiltonian
0 references
cycle
0 references
circuit
0 references
planar graph
0 references
edge coloring
0 references
cubic
0 references
three-regular
0 references