Spanning Trees and Domination in Hypercubes

Abstract: Let

L (G)

denote the maximum number of leaves in any spanning tree of a connected graph

G

. We show the (known) result that for the

n

-cube

Q_{n}

,

L (Q_{n}) s i m 2^{n} = | V (Q_{n}) |

as

n i g h t a r r o w i n f t y

. Examining this more carefully, consider the minimum size of a connected dominating set of vertices

g a m m a_{c} (Q_{n})

, which is

2^{n} - L (Q_{n})

for

n g e 2

. We show that

g a m m a_{c} (Q_{n}) s i m 2^{n} / n

. We use Hamming codes and an "expansion" method to construct leafy spanning trees in

Q_{n}

.

Recommendations

Cites work

Cited in

(6)

This page was built for publication: Spanning Trees and Domination in Hypercubes