Characterising k-connected sets in infinite graphs

J. Pascal Gollin, Karl Heuer

Research output: Contribution to journalJournal articleResearchpeer-review

76 Downloads (Pure)

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 ≤ k can be connected by 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.

Original languageEnglish
JournalJournal of Combinatorial Theory. Series B
Volume157
Pages (from-to)451-499
ISSN0095-8956
DOIs
Publication statusPublished - 2022

Keywords

  • Infinite graphs
  • Connectivity
  • Structural characterisation of families of graphs
  • k-Connected sets
  • k-Tree-width
  • Duality theorem

Fingerprint

Dive into the research topics of 'Characterising k-connected sets in infinite graphs'. Together they form a unique fingerprint.

Cite this