An official website of the United States government

Here’s how you know

Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock (
) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

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

Published

Author(s)

James Shook

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},\ldots,d_n})$, Jack Edmonds showed that there is a realization $G$ of $\pi$ 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 $\pi$ if $Z_0}$ is a spanning subgraph of $G_0}$ with $\delta(Z_0})\geq 1$ such that $|E(Z_0})|\geq 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})\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.