On a class of Hamiltonian laceable 3-regular graphs

DOI10.1016/0012-365X(94)00077-VMaRDI QIDQ1916371zbMATH OpenOpenAlexFDO

Authors C. C. Chen, K. L. McAvaney, Brian Alspach

Publication date 12 January 1997

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365x(94)00077-v

zbMATH Keywords

3-regular graphsbrick-productsCayley graphsdistanceHamiltonian path

Mathematics Subject Classification ID

Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Paths and cycles (05C38) Eulerian and Hamiltonian graphs (05C45)

Review text

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.

Recommendations

• Hamilton paths in Cayley graphs on generalized dihedral groups
• On edge-hamiltonian Cayley graphs
• Publication:5753983
• Hamilton paths in generalized Petersen graphs

Cited in

(14)

• Hamilton cycles and paths in vertex-transitive graphs-current directions
• The L(2,1)-labelling problem for cubic Cayley graphs on dihedral groups
• The Pfaffian property of Cayley graphs on dihedral groups
• Brian Alspach and his work
• Notes on the Hamiltonian property of dual graphs of 3-regular plane graphs
• Laceability and distance graphs
• Some Topics in Graph Theory
• Laceability properties in prism graphs
• LACEABILITY PROPERTIES IN FLOWER SNARK GRAPHS
• On r-dynamic chromatic number of some brick product graphs C(2n, 1, p)
• Cayley graphs of order \(kp\) are Hamiltonian for \(k < 48\)
• Hamilton-connected Cayley graphs on Hamiltonian groups
• Dead ends on wreath products and lamplighter groups
• Honeycomb toroidal graphs are Cayley graphs

This page was built for publication: On a class of Hamiltonian laceable 3-regular graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1916371)