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.

Full text available as:
[img]
Preview
PDF (Version of Record) - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
Download (578kB) | Preview
[img]
Preview
PDF (Version of Record) - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
Download (578kB) | Preview
[img]
Preview
PDF (Not Set) (Cover Page conversion from application/pdf to application/pdf) - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
Download (1MB) | Preview
[img]
Preview
PDF (Not Set) (Cover Page conversion from application/pdf to application/pdf) - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
Download (1MB) | Preview
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 2019 20:32
URI: http://oro.open.ac.uk/id/eprint/52560
Share this page:

Metrics

Altmetrics from Altmetric

Citations from Dimensions

Download history for this item

These details should be considered as only a guide to the number of downloads performed manually. Algorithmic methods have been applied in an attempt to remove automated downloads from the displayed statistics but no guarantee can be made as to the accuracy of the figures.

Actions (login may be required)

Policies | Disclaimer

© The Open University   contact the OU