Maximally edge‐connected realizations and Kundu's k k‐factor theorem

Abstract: A simple graph

G

with edge-connectivity

l a m b d a (G)

and minimum degree

d e l t a (G)

is maximally edge connected if

l a m b d a (G) = d e l t a (G)

. In 1964, given a non-increasing degree sequence

p i = (d_{1}, l d o t s, d_{n})

, Jack Edmonds showed that there is a realization

G

of

p i

that is

k

-edge-connected if and only if

d_{n} g e q k

with

s u m_{i = 1}^{n} d_{i} g e q 2 (n - 1)

when

d_{n} = 1

. We strengthen Edmonds's result by showing that given a realization

G_{0}

of

p i

if

Z_{0}

is a spanning subgraph of

G_{0}

with

d e l t a (Z_{0}) g e q 1

such that

| E (Z_{0}) | g e q n - 1

when

d e l t a (G_{0}) = 1

, then there is a maximally edge-connected realization of

p i

with

G_{0} - E (Z_{0})

as a subgraph. Our theorem tells us that there is a maximally edge-connected realization of

p i

that differs from

G_{0}

by at most

n - 1

edges. For

d e l t a (G_{0}) g e q 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 find maximally edge-connected realizations with a

(k_{1}, d o t s, k_{n})

-factor for

k l e q k_{i} l e q k + 1

and present a partial result to a conjecture that strengthens the regular case of Kundu's

k

-factor theorem.

Recommendations

Cites work

Cited in

(1)

This page was built for publication: Maximally edge‐connected realizations and Kundu's k $k$‐factor theorem