Premium
On Hamilton decompositions of infinite circulant graphs
Author(s) -
Bryant Darryn,
Herke Sarada,
Maenhaut Barbara,
Webb Bridget S.
Publication year - 2018
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22223
Subject(s) - circulant matrix , mathematics , combinatorics , circulant graph , hamiltonian path , disjoint sets , discrete mathematics , finite set , graph , line graph , voltage graph , mathematical analysis
The natural infinite analog of a (finite) Hamilton cycle is a two‐way‐infinite Hamilton path (connected spanning 2‐valent subgraph). Although it is known that every connected 2 k ‐valent infinite circulant graph has a two‐way‐infinite Hamilton path, there exist many such graphs that do not have a decomposition into k edge‐disjoint two‐way‐infinite Hamilton paths. This contrasts with the finite case where it is conjectured that every 2 k ‐valent connected circulant graph has a decomposition into k edge‐disjoint Hamilton cycles. We settle the problem of decomposing 2 k ‐valent infinite circulant graphs into k edge‐disjoint two‐way‐infinite Hamilton paths for k = 2 , in many cases when k = 3 , and in many other cases including where the connection set is ± { 1 , 2 , … , k } or ± { 1 , 2 , … , k − 1 , k + 1 } .