2013/05/06 by Dániel Marx, Marx, Daniel, Paul Wollan +1 · 1 citation
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Interconnection Networks and Systems
paper · pdf · doi:10.48550/arxiv.1305.1331
We consider the problem of how much edge connectivity is necessary to force a graph G to contain a fixed graph H as an immersion. We show that if the maximum degree in H is D, then all the examples of D-edge connected graphs which do not contain H as a weak immersion must have a tree-like decomposition called a tree-cut decomposition of bounded width. If we consider strong immersions, then it is easy to see that there are arbitrarily highly edge connected graphs which do not contain a fixed clique Kt as a strong immersion. We give a structure theorem which roughly characterizes those highly edge connected graphs which do not contain Kt as a strong immersion.