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.
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 language | English |
---|---|
Journal | Journal of Combinatorial Theory. Series B |
Volume | 157 |
Pages (from-to) | 451-499 |
ISSN | 0095-8956 |
DOIs | |
Publication status | Published - 2022 |
Keywords
- Infinite graphs
- Connectivity
- Structural characterisation of families of graphs
- k-Connected sets
- k-Tree-width
- Duality theorem