We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
On Hamilton decompositions of infinite circulant graphs.
- Authors
Bryant, Darryn; Herke, Sarada; Maenhaut, Barbara; Webb, Bridget S.
- Abstract
Abstract: 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<italic>k</italic>‐valent infinite circulant graph has a two‐way‐infinite Hamilton path, there exist many such graphs that do not have a decomposition into <italic>k</italic> edge‐disjoint two‐way‐infinite Hamilton paths. This contrasts with the finite case where it is conjectured that every 2<italic>k</italic>‐valent connected circulant graph has a decomposition into <italic>k</italic> edge‐disjoint Hamilton cycles. We settle the problem of decomposing 2<italic>k</italic>‐valent infinite circulant graphs into <italic>k</italic> 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 }.
- Subjects
HAMILTONIAN graph theory; MATHEMATICAL decomposition; SUBGRAPHS; GRAPH connectivity; PATHS &; cycles in graph theory; GRAPH theory
- Publication
Journal of Graph Theory, 2018, Vol 88, Issue 3, p434
- ISSN
0364-9024
- Publication type
Article
- DOI
10.1002/jgt.22223