Forcing highly connected subgraphs
Forcing highly connected subgraphs
复制标题
强制高度连接的子图
DOI：
10.1002/jgt.20216
复制
发表时间：
2007
影响因子：
0.9
通讯作者：
M. Stein
中科院分区：
文献类型：
--
作者：
M. Stein
Mader的一个定理表明，在有限图中，高度连通的子图可以通过假设一个高的最小度而被强制。我们把这个结果推广到无限图。在这里，不仅需要顶点的高度，而且需要图的端点的高顶点度（或多重度），即在每一端有大量不相交的射线。我们给出了顶点度的下界和端点的顶点度的下界，它在k中是二次的，即期望子图的连通性。事实上，这离最好的可能也不远了：我们展示了一组图，顶点的度数为2k阶，端点的顶点度数为k log k阶，它们没有k个连通的子图。
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 2k at the vertices and a vertex‐degree of order k log k at the ends which have no k‐connected subgraphs.