Maximally Edge-Connected Realizations and Kundu's $k$-factor Theorem

Abstract

A simple graph $G$ with edge-connectivity $\lambda (G)$ and minimum degree $\delta (G)$ is maximally edge connected if $\lambda (G)=\delta (G)$. In 1964, given a non-increasing degree sequence $\pi =(d_1,\dots ,d_n)$, Jack Edmonds showed that there is a realization $G$ of $\pi$ that is $k$-edge-connected if and only if $d_n\ge k$ with ${\sum }_{i=1}^n{d}_i\ge 2(n-1)$ when $d_n=1$. We strengthen Edmonds's result by showing that given a realization $G_0$ of $\pi$ if $Z_0$ is a spanning subgraph of $G_0$ with $\delta (Z_0)\ge 1$ such that $|E(Z_0)|\ge n-1$ when $\delta (G_0)=1$, then there is a maximally edge-connected realization of $\pi$ with $G_0-E(Z_0)$ as a subgraph. Our theorem tells us that there is a maximally edge-connected realization of $\pi$ that differs from $G_0$ by at most $n-1$ edges. For $\delta (G_0)\ge 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\le k_i\le k+1$ and present a partial result to a conjecture that strengthens the regular case of Kundu's $k$-factor theorem.

arXiv comment13 pages, 1 figure

Cited by in corpus (1)

• On a conjecture that strengthens Kundu's $k$-factor Theorem