On a class of Hamiltonian laceable 3-regular graphs (Q1916371)

Alspach and Zhang showed that all Cayley graphs over dihedral groups with minimal generating sets consisting of 3 elements are Hamiltonian. When the elements are of order 2, the graph is a ``brick-product'', denoted \(C(2n, m, r)\), made up of \(m\) copies of the cycle \(C_{2n}= 012\dots(2n- 1)0\) and certain edges (``chords'') specified using \(r\). They conjectured that all brick-products are such that each pair of vertices an odd distance apart are joined by a Hamiltonian path. This paper considers the problem for \(m= 1\), where the chordal edges are \(2k(2k+ r)\), \(k= 1,\dots, n\). It is shown that most \(C(2n, 1, r)\) have the desired property. For example, the conjecture holds for \(r= 3, 5, 7, 9\) and for all \(n\) sufficiently large in relation to \(r\). To handle each case, paths joining odd-distanced vertices are explicitly constructed.