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

Published

August 3, 2023

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.

Citation

Journal of Graph Theory

Volume

105

Issue

1

Pub Type

Journals

Download Paper

https://doi.org/10.1002/jgt.23017

Local Download

Keywords

graph theory, degree sequence, edge-connected, maximally edge-connected, k-factor

Citation

Shook, J. (2023), Maximally Edge-Connected Realizations and Kundu's k-factor Theorem, Journal of Graph Theory, [online], https://doi.org/10.1002/jgt.23017, https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=933480 (Accessed October 10, 2025)