Premium
Forcing highly connected subgraphs
Author(s) -
Stein Maya Jakobine
Publication year - 2007
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20216
Subject(s) - combinatorics , mathematics , degree (music) , discrete mathematics , vertex (graph theory) , counterexample , upper and lower bounds , graph , mathematical analysis , physics , acoustics
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