Orientations of infinite graphs with prescribed edge-connectivity

Carsten Thomassen

doi:10.1007/s00493-015-3173-0

Orientations of infinite graphs with prescribed edge-connectivity

Carsten Thomassen

Research output: Contribution to journal › Journal article › Research › peer-review

501 Downloads (Pure)

Abstract

We prove a decomposition result for locally finite graphs which can be used to extend results on edge-connectivity from finite to infinite graphs. It implies that every 4k-edge-connected graph G contains an immersion of some finite 2k-edge-connected Eulerian graph containing any prescribed vertex set (while planar graphs show that G need not containa subdivision of a simple finite graph of large edge-connectivity). Also, every 8k-edge connected infinite graph has a k-arc-connected orientation, as conjectured in 1989.

Original language	English
Journal	Combinatorica
Volume	36
Issue number	5
Pages (from-to)	601–621
Number of pages	21
ISSN	0209-9683
DOIs	https://doi.org/10.1007/s00493-015-3173-0
Publication status	Published - 2016

Access to Document

10.1007/s00493-015-3173-0

Inf orient finalAccepted author manuscript, 239 KB

Fingerprint Dive into the research topics of 'Orientations of infinite graphs with prescribed edge-connectivity'. Together they form a unique fingerprint.

Cite this

@article{c7dab84e3c214ed2a00f44f3754f2105,

title = "Orientations of infinite graphs with prescribed edge-connectivity",

abstract = "We prove a decomposition result for locally finite graphs which can be used to extend results on edge-connectivity from finite to infinite graphs. It implies that every 4k-edge-connected graph G contains an immersion of some finite 2k-edge-connected Eulerian graph containing any prescribed vertex set (while planar graphs show that G need not containa subdivision of a simple finite graph of large edge-connectivity). Also, every 8k-edge connected infinite graph has a k-arc-connected orientation, as conjectured in 1989.",

author = "Carsten Thomassen",

year = "2016",

doi = "10.1007/s00493-015-3173-0",

language = "English",

volume = "36",

pages = "601–621",

journal = "Combinatorica",

issn = "0209-9683",

publisher = "Springer",

number = "5",

}

TY - JOUR

T1 - Orientations of infinite graphs with prescribed edge-connectivity

AU - Thomassen, Carsten

PY - 2016

Y1 - 2016

N2 - We prove a decomposition result for locally finite graphs which can be used to extend results on edge-connectivity from finite to infinite graphs. It implies that every 4k-edge-connected graph G contains an immersion of some finite 2k-edge-connected Eulerian graph containing any prescribed vertex set (while planar graphs show that G need not containa subdivision of a simple finite graph of large edge-connectivity). Also, every 8k-edge connected infinite graph has a k-arc-connected orientation, as conjectured in 1989.

AB - We prove a decomposition result for locally finite graphs which can be used to extend results on edge-connectivity from finite to infinite graphs. It implies that every 4k-edge-connected graph G contains an immersion of some finite 2k-edge-connected Eulerian graph containing any prescribed vertex set (while planar graphs show that G need not containa subdivision of a simple finite graph of large edge-connectivity). Also, every 8k-edge connected infinite graph has a k-arc-connected orientation, as conjectured in 1989.

U2 - 10.1007/s00493-015-3173-0

DO - 10.1007/s00493-015-3173-0

M3 - Journal article

VL - 36

SP - 601

EP - 621

JO - Combinatorica

JF - Combinatorica

SN - 0209-9683

IS - 5

ER -