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^*

^*Korrespondierende/r Autor/-in für diese Arbeit

Publikation: Beitrag in einer Fachzeitschrift › Artikel › Begutachtung

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.

Originalsprache	englisch
Seiten (von - bis)	171-191
Seitenumfang	21
Fachzeitschrift	Journal of Combinatorial Theory, Series B
Jahrgang	140
DOIs	https://doi.org/10.1016/j.jctb.2019.05.005
Publikationsstatus	Veröffentlicht - Jan. 2020
Extern publiziert	Ja

ASJC Scopus subject areas

Theoretische Informatik
Diskrete Mathematik und Kombinatorik
Theoretische Informatik und Mathematik

Fields of Expertise

Information, Communication & Computing

Zugriff auf Dokument

10.1016/j.jctb.2019.05.005

https://arxiv.org/abs/1709.09463

Andere Dateien und Links

FWF - Groups - Graphen und Gruppen
Lehner, F.
1/04/19 → 31/12/20
Projekt: Forschungsprojekt

Dieses zitieren

@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

ASJC Scopus subject areas

Fields of Expertise

Zugriff auf Dokument

Andere Dateien und Links

Fingerprint

Projekte

FWF - Groups - Graphen und Gruppen

Dieses zitieren