Forcing highly connected subgraphs

✍ Scribed by Maya Jakobine Stein

• Publisher: John Wiley and Sons
• Year: 2007
• Tongue: English
• Weight: 228 KB
• Volume: 54
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.20216

✦ Synopsis

Abstract

A theorem of Mader states that highly connected subgraphs can be forced in finite graphs by assuming a high minimum degree. We extend this result to infinite graphs. Here, it is necessary to require not only high degree for the vertices but also high vertex‐degree (or multiplicity) for the ends of the graph, that is, a large number of disjoint rays in each end. We give a lower bound on the degree of vertices and the vertex‐degree of the ends which is quadratic in k, the connectedness of the desired subgraph. In fact, this is not far from best possible: we exhibit a family of graphs with a degree of order 2^k^ at the vertices and a vertex‐degree of order k log k at the ends which have no k‐connected subgraphs.

Furthermore, if in addition to the high degrees at the vertices, we only require high edge‐degree for the ends (which is defined as the maximum number of edge‐disjoint rays in an end), Mader's theorem does not extend to infinite graphs, not even to locally finite ones. We give a counterexample in this respect. But, assuming a lower bound of at least 2__k__ for the edge‐degree at the ends and the degree at the vertices does suffice to ensure the existence (k + 1)‐edge‐connected subgraphs in arbitrary graphs. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 331–349, 2007