On the number of forests and connected spanning subgraphs

Abstract: Let

F (G)

be the number of forests of a graph

G

. Similarly let

C (G)

be the number of connected spanning subgraphs of a connected graph

G

. We bound

F (G)

and

C (G)

for regular graphs and for graphs with fixed average degree. Among many other things we study

f_{d} = s u p_{G i n m a t h c a l G_{d}} F (G)^{1 / v (G)}

, where

m a t h c a l G_{d}

is the family of

d

--regular graphs, and

v (G)

denotes the number of vertices of a graph

G

. We show that

f_{3} = 2^{3 / 2}

, and if

(G_{n})_{n}

is a sequence of

3

--regular graphs with length of the shortest cycle tending to infinity, then

l i m_{n o i n f t y} F (G_{n})^{1 / v (G_{n})} = 2^{3 / 2}

. We also improve on the previous best bounds on

f_{d}

for

4 l e q d l e q 9

.

Recommendations

Cites Work

Cited In (13)

This page was built for publication: On the number of forests and connected spanning subgraphs