2018/11/15 by Gollin, J. Pascal, Heuer, Karl
#05C40 #05C63 #05C75 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1811.06411
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.