The Lovász-Cherkassky theorem for locally finite graphs with ends

Raphael W. Jacobs; Attila Joó; Paul Knappe; Jan Kurkofka; Ruben Melcher

doi:10.1016/j.disc.2023.113586

The Lovász-Cherkassky theorem for locally finite graphs with ends

Raphael W. Jacobs^*, Attila Joó^*, Paul Knappe^*, Jan Kurkofka^*, Ruben Melcher

^*Corresponding author for this work

Mathematics

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

Abstract

Lovász and Cherkassky discovered independently that, if G is a finite graph and T ⊆ V(G) such that the degree d_G(v) is even for every vertex v ∈ V(G) \ T, then the maximum number of edge-disjoint paths which are internally disjoint from T and connect distinct vertices of T is equal to ½ Σ_t∈T λ_G(t, T \ {t}) (where λ_G(t, T \ {t}) is the size of a smallest cut that separates t and T \ {t}). From another perspective, this means that for every vertex t ∈ T , in any optimal path-system there are λ_G (t, T \ {t}) many paths between t and T \ {t}. We extend the theorem of Lovász and Cherkassky based on this reformulation to all locally-finite infinite graphs and their ends. In our generalisation, T may contain not just vertices but ends as well, and paths are one-way (two-way) infinite when they establish a vertex-end (end-end) connection.

Original language	English
Article number	113586
Number of pages	6
Journal	Discrete Mathematics
Volume	346
Issue number	12
Early online date	10 Jul 2023
DOIs	https://doi.org/10.1016/j.disc.2023.113586
Publication status	Published - Dec 2023

Keywords

Lovász-Cherkassky theorem
Infinite graph
Freudenthal compactification
Edge-connectivity

Access to Document

10.1016/j.disc.2023.113586Licence: None: All rights reserved

Cite this

@article{57e95ba3867e428c98297de99fb5c888,

title = "The Lov{\'a}sz-Cherkassky theorem for locally finite graphs with ends",

abstract = "Lov{\'a}sz and Cherkassky discovered independently that, if G is a finite graph and T ⊆ V(G) such that the degree dG(v) is even for every vertex v ∈ V(G) \ T, then the maximum number of edge-disjoint paths which are internally disjoint from T and connect distinct vertices of T is equal to ½ Σt∈T λG(t, T \ {t}) (where λG(t, T \ {t}) is the size of a smallest cut that separates t and T \ {t}). From another perspective, this means that for every vertex t ∈ T , in any optimal path-system there are λG (t, T \ {t}) many paths between t and T \ {t}. We extend the theorem of Lov{\'a}sz and Cherkassky based on this reformulation to all locally-finite infinite graphs and their ends. In our generalisation, T may contain not just vertices but ends as well, and paths are one-way (two-way) infinite when they establish a vertex-end (end-end) connection. ",

keywords = "Lov{\'a}sz-Cherkassky theorem, Infinite graph, Freudenthal compactification, Edge-connectivity",

author = "Jacobs, {Raphael W.} and Attila Jo{\'o} and Paul Knappe and Jan Kurkofka and Ruben Melcher",

year = "2023",

month = dec,

doi = "10.1016/j.disc.2023.113586",

language = "English",

volume = "346",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier",

number = "12",

}

TY - JOUR

T1 - The Lovász-Cherkassky theorem for locally finite graphs with ends

AU - Jacobs, Raphael W.

AU - Joó, Attila

AU - Knappe, Paul

AU - Kurkofka, Jan

AU - Melcher, Ruben

PY - 2023/12

Y1 - 2023/12

N2 - Lovász and Cherkassky discovered independently that, if G is a finite graph and T ⊆ V(G) such that the degree dG(v) is even for every vertex v ∈ V(G) \ T, then the maximum number of edge-disjoint paths which are internally disjoint from T and connect distinct vertices of T is equal to ½ Σt∈T λG(t, T \ {t}) (where λG(t, T \ {t}) is the size of a smallest cut that separates t and T \ {t}). From another perspective, this means that for every vertex t ∈ T , in any optimal path-system there are λG (t, T \ {t}) many paths between t and T \ {t}. We extend the theorem of Lovász and Cherkassky based on this reformulation to all locally-finite infinite graphs and their ends. In our generalisation, T may contain not just vertices but ends as well, and paths are one-way (two-way) infinite when they establish a vertex-end (end-end) connection.

AB - Lovász and Cherkassky discovered independently that, if G is a finite graph and T ⊆ V(G) such that the degree dG(v) is even for every vertex v ∈ V(G) \ T, then the maximum number of edge-disjoint paths which are internally disjoint from T and connect distinct vertices of T is equal to ½ Σt∈T λG(t, T \ {t}) (where λG(t, T \ {t}) is the size of a smallest cut that separates t and T \ {t}). From another perspective, this means that for every vertex t ∈ T , in any optimal path-system there are λG (t, T \ {t}) many paths between t and T \ {t}. We extend the theorem of Lovász and Cherkassky based on this reformulation to all locally-finite infinite graphs and their ends. In our generalisation, T may contain not just vertices but ends as well, and paths are one-way (two-way) infinite when they establish a vertex-end (end-end) connection.

KW - Lovász-Cherkassky theorem

KW - Infinite graph

KW - Freudenthal compactification

KW - Edge-connectivity

U2 - 10.1016/j.disc.2023.113586

DO - 10.1016/j.disc.2023.113586

M3 - Article

SN - 0012-365X

VL - 346

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 12

M1 - 113586

ER -

The Lovász-Cherkassky theorem for locally finite graphs with ends

Abstract

Keywords

Access to Document

Fingerprint

Cite this