Infinite Hamiltonian paths in Cayley digraphs

✍ Scribed by Irwin L Jungreis

• Publisher: Elsevier Science
• Year: 1985
• Tongue: English
• Weight: 942 KB
• Volume: 54
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(85)90078-0

✦ Synopsis

Let Cay(S : H) be the Cayley digraph of the generators S in the group H. A one-way infinite Hamiltonian path in the digraph G is a listing of all the vertices [q: 1 ~< i <oo], such that there is an arc from vi to vi+ 1. A two-way infinite Hamiltonian path is similarly defined, with i ranging from -0o to oo. In this paper, we give conditions on S and H for the existence of one-and two-way infinite Hamiltonian paths in Cay(S:H). Two of our results can be summarized as follows. First, if S is countably infinite and H is abelian, then Cay(S : H) has one-and two-way Hamiltonian paths if and only if it is strongly connected (except for one infinite family). We also give necessary and sufficient conditions on S for Cay(S :H) to be strongly connected for a large class of Cayley digraphs. Second, we show that any Cayley digraph of a countable locally finite group has both one-and two-way infinite Hamiltonian paths. As a lemma, we give a relation between the strong connectivity and the outer valence of finite vertex-transitive digraphs.