The Open UniversitySkip to content
 

On Hamilton decompositions of infinite circulant graphs

Bryant, Darryn; Herke, Sarada; Maenhaut, Barbara and Webb, Bridget S. (2018). On Hamilton decompositions of infinite circulant graphs. Journal of Graph Theory, 88(3) pp. 434–448.

DOI (Digital Object Identifier) Link: https://doi.org/10.1002/jgt.22223
Google Scholar: Look up in Google Scholar

Abstract

The natural infinite analogue of a (finite) Hamilton cycle is a two-way-infinite Hamilton path (connected spanning 2-valent subgraph). Although it is known that every connected 2k-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 2k-valent connected circulant graph has a decomposition into k edge-disjoint Hamilton cycles. We settle the problem of decomposing 2k-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, 1,2,...,k + 1}.

Item Type: Journal Item
Copyright Holders: 2017 The Authors
ISSN: 0364-9024
Project Funding Details:
Funded Project NameProject IDFunding Body
Homogeneous Steiner triple systemsEP/M016242/1EPSRC (Engineering and Physical Sciences Research Council)
Not SetDP150100530ARC Australian Research Council
Not SetDP150100506ARC Australian Research Council
Not SetDP120100790ARC Australian Research Council
Not SetDP130102987ARC Australian Research Council
Academic Unit/School: Faculty of Science, Technology, Engineering and Mathematics (STEM) > Mathematics and Statistics
Faculty of Science, Technology, Engineering and Mathematics (STEM)
Item ID: 52560
Depositing User: Bridget Webb
Date Deposited: 14 Feb 2018 16:57
Last Modified: 19 Sep 2018 17:41
URI: http://oro.open.ac.uk/id/eprint/52560
Share this page:

Metrics

Altmetrics from Altmetric

Citations from Dimensions

Actions (login may be required)

Policies | Disclaimer

© The Open University   contact the OU