Globally balancing spanning trees

Publication date 28 December 2022

Abstract: We show that for every graph

G

that contains two edge-disjoint spanning trees, we can choose two edge-disjoint spanning trees

T_{1}, T_{2}

of

G

such that

| d_{T_{1}} (v) - d_{T_{2}} (v) | l e q 5

for all

v i n V (G)

. We also prove the more general statement that for every positive integer

k

, there is a constant

c_{k} i n O (l o g k)

such that for every graph

G

that contains

k

edge-disjoint spanning trees, we can choose

k

edge-disjoint spanning trees

T_{1}, l d o t s, T_{k}

of

G

satisfying

| d_{T_{i}} (v) - d_{T_{j}} (v) | l e q c_{k}

for all

v i n V (G)

and

i, j i n 1, l d o t s, k

. This resolves a conjecture of Kriesell.

Recommendations

Cites work

Cited in

(4)

This page was built for publication: Globally balancing spanning trees