Characterising k-connected sets in infinite graphs

DOI10.1016/J.JCTB.2022.08.004MaRDI QIDQ2171028zbMATH OpenOpenAlexFDO

Authors J. Pascal Gollin, Karl Heuer

Publication date 23 September 2022

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1811.06411

zbMATH Keywords

\(k\)-connected sets\(k\)-tree-widthconnectivityduality theoreminfinite graphsstructural characterisation of families of graphs

Mathematics Subject Classification ID

Connectivity (05C40) Infinite graphs (05C63) Structural characterization of families of graphs (05C75)

Abstract: A $k$-connected set in an infinite graph, where $k>0$ is an integer, is a set of vertices such that any two of its subsets of the same size $ellleqk$ can be connected by $ell$ disjoint paths in the whole graph. We characterise the existence of $k$-connected sets of arbitrary but fixed infinite cardinality via the existence of certain minors and topological minors. We also prove a duality theorem for the existence of such $k$-connected sets: if a graph contains no such $k$-connected set, then it has a tree-decomposition which, whenever it exists, precludes the existence of such a $k$-connected set.

Recommendations

• Publication:3204497
• Large k‐preserving sets in infinite graphs
• High connectivity keeping sets in \(n\)-connected graphs
• Ends and vertices of small degree in infinite minimally k-(Edge)-connected graphs
• The degree sets of connected infinite graphs

Cites work

• \(k\)-blocks: a connectivity invariant for graphs
• A Menger-like property of tree-width: The finite case
• Extremal infinite graph theory
• Graph theory
• Graph-theoretical versus topological ends of graphs.
• Highly connected sets and the excluded grid theorem
• scientific article; zbMATH DE number 1870231 (Why is no real title available?)
• Infinite end-devouring sets of rays with prescribed start vertices
• Profinite separation systems
• Quickly excluding a planar graph
• Representations of infinite tree sets
• Set theory. An introduction to independence proofs
• Simplicial Decompositions of Infinite Graphs
• The Menger-like property of the three-width of infinite graphs
• Tree sets
• Typical subgraphs of 3- and 4-connected graphs
• Über die Maximalzahl fremder unendlicher Wege in Graphen

Cited in

(13)

• Halin's end degree conjecture
• scientific article; zbMATH DE number 4181381 (Why is no real title available?)
• scientific article; zbMATH DE number 6019705 (Why is no real title available?)
• The degree sets of connected infinite graphs
• scientific article; zbMATH DE number 15670 (Why is no real title available?)
• Large k‐preserving sets in infinite graphs
• Duality theorems for stars and combs I: Arbitrary stars and combs
• Unavoidable topological minors of infinite graphs
• Ubiquity of graphs with nowhere‐linear end structure
• Efficiently distinguishing all tangles in locally finite graphs
• The excluded minors for embeddability into a compact surface
• A representation theorem for end spaces of infinite graphs
• An end degree for digraphs

This page was built for publication: Characterising \(k\)-connected sets in infinite graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2171028)