Construction of Hamiltonian cycles in layered cubic planar graphs (Q1606028): Difference between revisions

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\).