Hamilton decompositions of one-ended Cayley graphs

Joshua Erde; Florian Lehner; Max Pitz

doi:10.1016/j.jctb.2019.05.005

Hamilton decompositions of one-ended Cayley graphs

Joshua Erde^*, Florian Lehner^*, Max Pitz^*

^*Corresponding author for this work

Research output: Contribution to journal › Article › peer-review

Abstract

We prove that any one-ended, locally finite Cayley graph G(Γ,S), where Γ is an abelian group and S is a finite generating set of non-torsion elements, admits a decomposition into edge-disjoint Hamiltonian (i.e. spanning) double-rays. In particular, the n-dimensional grid Z ⁿ admits a decomposition into n edge-disjoint Hamiltonian double-rays for all n∈N.

Original language	English
Pages (from-to)	171-191
Number of pages	21
Journal	Journal of Combinatorial Theory, Series B
Volume	140
DOIs	https://doi.org/10.1016/j.jctb.2019.05.005
Publication status	Published - Jan 2020
Externally published	Yes

Keywords

Alspach conjecture
Cayley graph
Double ray
Hamilton decomposition

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Fields of Expertise

Information, Communication & Computing

Access to Document

10.1016/j.jctb.2019.05.005

https://arxiv.org/abs/1709.09463

Cite this

@article{16d36dbb7c744f0dbc081d95b8ebc20e,

title = "Hamilton decompositions of one-ended Cayley graphs",

abstract = "We prove that any one-ended, locally finite Cayley graph G(Γ,S), where Γ is an abelian group and S is a finite generating set of non-torsion elements, admits a decomposition into edge-disjoint Hamiltonian (i.e. spanning) double-rays. In particular, the n-dimensional grid Z n admits a decomposition into n edge-disjoint Hamiltonian double-rays for all n∈N. ",

keywords = "Alspach conjecture, Cayley graph, Double ray, Hamilton decomposition",

author = "Joshua Erde and Florian Lehner and Max Pitz",

year = "2020",

month = jan,

doi = "10.1016/j.jctb.2019.05.005",

language = "English",

volume = "140",

pages = "171--191",

journal = "Journal of Combinatorial Theory, Series B",

issn = "0095-8956",

publisher = "Elsevier B.V.",

}

TY - JOUR

T1 - Hamilton decompositions of one-ended Cayley graphs

AU - Erde, Joshua

AU - Lehner, Florian

AU - Pitz, Max

PY - 2020/1

Y1 - 2020/1

N2 - We prove that any one-ended, locally finite Cayley graph G(Γ,S), where Γ is an abelian group and S is a finite generating set of non-torsion elements, admits a decomposition into edge-disjoint Hamiltonian (i.e. spanning) double-rays. In particular, the n-dimensional grid Z n admits a decomposition into n edge-disjoint Hamiltonian double-rays for all n∈N.

AB - We prove that any one-ended, locally finite Cayley graph G(Γ,S), where Γ is an abelian group and S is a finite generating set of non-torsion elements, admits a decomposition into edge-disjoint Hamiltonian (i.e. spanning) double-rays. In particular, the n-dimensional grid Z n admits a decomposition into n edge-disjoint Hamiltonian double-rays for all n∈N.

KW - Alspach conjecture

KW - Cayley graph

KW - Double ray

KW - Hamilton decomposition

UR - https://www.sciencedirect.com/science/article/pii/S0095895619300541

UR - http://www.scopus.com/inward/record.url?scp=85066988426&partnerID=8YFLogxK

U2 - 10.1016/j.jctb.2019.05.005

DO - 10.1016/j.jctb.2019.05.005

M3 - Article

SN - 0095-8956

VL - 140

SP - 171

EP - 191

JO - Journal of Combinatorial Theory, Series B

JF - Journal of Combinatorial Theory, Series B

ER -

Hamilton decompositions of one-ended Cayley graphs

Abstract

Keywords

ASJC Scopus subject areas

Fields of Expertise

Access to Document

Other files and links

Fingerprint

FWF - Groups - Graphs and Groups

Cite this

Hamilton decompositions of one-ended Cayley graphs

Abstract

Keywords

ASJC Scopus subject areas

Fields of Expertise

Access to Document

Other files and links

Fingerprint

Projects

FWF - Groups - Graphs and Groups

Cite this