Hamilton paths in Cayley graphs on Coxeter groups: I

Brian Alspach


We consider several families of Cayley graphs on the finite Coxeter groups An, Bn,  and Dn with regard to the problem of whether they are Hamilton-laceable or Hamilton-connected. It is known that every connected bipartite Cayley graph on An, n ≥ 2, whose connection set contains only transpositions and has valency at least three is Hamilton-laceable. We obtain analogous results for connected bipartite Cayley graphs on Bn, and for connected Cayley graphs on Dn. Non-bipartite examples arise for the latter family.


Hamilton path, Cayley graph, Coxeter group, Hamilton-connected, Hamilton-laceable

Full Text:


DOI: https://doi.org/10.26493/1855-3974.509.d9d

ISSN: 1855-3974

Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications