The number of bounded‐degree spanning trees

Abstract: For a graph

G

, let

c_{k} (G)

be the number of spanning trees of

G

with maximum degree at most

k

. For

k g e 3

, it is proved that every connected

n

-vertex

r

-regular graph

G

with

r g e f r a c n k + 1

satisfies

c_k(G)^{1/n} ge (1-o_n(1)) r cdot z_k

where

z_{k} > 0

approaches

1

extremely fast (e.g.

z_{10} = 0.999971

). The minimum degree requirement is essentially tight as for every

k g e 2

there are connected

n

-vertex

r

-regular graphs

G

with

r = l f l o o r n / (k + 1) f l o o r - 2

for which

c_{k} (G) = 0

. Regularity may be relaxed, replacing

r

with the geometric mean of the degree sequence and replacing

z_{k}

with

z_{k}^{*} > 0

that also approaches

1

, as long as the maximum degree is at most

n (1 - (3 + o_{k} (1)) s q r t l n k / k)

. The same holds with no restriction on the maximum degree as long as the minimum degree is at least

f r a c n k (1 + o_{k} (1))

.

Recommendations

Cites work

Cited in

(13)

This page was built for publication: The number of bounded‐degree spanning trees