论文标题
最大边缘连接的实现和Kundu的$ k $ -factor定理
Maximally Edge-Connected Realizations and Kundu's $k$-factor Theorem
论文作者
论文摘要
一个简单的图形$ g $，带有边缘连接性$λ（g）$和最低度$δ（g）$，如果$λ（g）=δ（g）$，则最大值连接。 1964年，给定非侵入度序列$π=（d_ {1}，\ ldots，d_ {n}）$，杰克·埃德蒙兹（Jack Edmonds $ \ sum_ {i = 1}^{n} d_ {i} \ geq 2（n-1）$当$ d_ {n} = 1 $时。如果$ z_ {0} $是$ g_ {0} $，$ g_ {0} $带有$δ（z__ {0}）\ geq 1 $，$ g_ {0} $是$ g_ {0} $，我们通过证明$ g_ {0} $ of $π$来增强埃德蒙兹的结果，并增强埃德蒙兹的结果。 $ g_ {0} -e（z_ {0}）$作为子图的最大边缘连接实现$π$。我们的定理告诉我们，$π$的最大边缘连接实现与$ g_ {0} $不同，最多在$ n-1 $边缘。对于$δ（g_ {0}）\ geq 2 $，如果$ g_ {0} $具有带有$ c $组件的跨度森林，那么我们的定理说，最大边缘连接的认识与$ g_ {0} $不同，最多在$ n-c $ edges上。作为一个应用程序，我们将工作与Kundu的$ k $ -factor定理相结合，以表明有一个最大边缘连接的实现，以及$（k_ {1}，\ dots，k_ {n}）$ - $ k \ leq k_ {iq k_ {i} \ leq k+1 $ and part a a $ $ kund to to to to n of to to to n of to n of $ k_ {n}）$ - 定理。
A simple graph $G$ with edge-connectivity $λ(G)$ and minimum degree $δ(G)$ is maximally edge connected if $λ(G)=δ(G)$. In 1964, given a non-increasing degree sequence $π=(d_{1},\ldots,d_{n})$, Jack Edmonds showed that there is a realization $G$ of $π$ that is $k$-edge-connected if and only if $d_{n}\geq k$ with $\sum_{i=1}^{n}d_{i}\geq 2(n-1)$ when $d_{n}=1$. We strengthen Edmonds's result by showing that given a realization $G_{0}$ of $π$ if $Z_{0}$ is a spanning subgraph of $G_{0}$ with $δ(Z_{0})\geq 1$ such that $|E(Z_{0})|\geq n-1$ when $δ(G_{0})=1$, then there is a maximally edge-connected realization of $π$ with $G_{0}-E(Z_{0})$ as a subgraph. Our theorem tells us that there is a maximally edge-connected realization of $π$ that differs from $G_{0}$ by at most $n-1$ edges. For $δ(G_{0})\geq 2$, if $G_{0}$ has a spanning forest with $c$ components, then our theorem says there is a maximally edge-connected realization that differs from $G_{0}$ by at most $n-c$ edges. As an application we combine our work with Kundu's $k$-factor Theorem to show there is a maximally edge-connected realization with a $(k_{1},\dots,k_{n})$-factor for $k\leq k_{i}\leq k+1$ and present a partial result to a conjecture that strengthens the regular case of Kundu's $k$-factor theorem.
