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

Mathematics

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

Bibliographical note

Publisher Copyright:
© 2019 Elsevier Inc.

Keywords

Alspach conjecture
Cayley graph
Double ray
Hamilton decomposition

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Access to Document

10.1016/j.jctb.2019.05.005

Cite this

@article{b03de8a84c3f418a88a4bd1b758f2131,

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 Zn 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",

note = "Publisher Copyright: {\textcopyright} 2019 Elsevier Inc.",

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",

}

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 Zn 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 Zn 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.scopus.com/pages/publications/85066988426

U2 - 10.1016/j.jctb.2019.05.005

DO - 10.1016/j.jctb.2019.05.005

M3 - Article

AN - SCOPUS:85066988426

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

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Fingerprint

Cite this