Geodesic
On the spanning trees of the hypercube and other products of graphs
Olivier Bernardi1
1Brandeis University
The electronic journal of combinatorics, Tome 19 (2012) no. 4
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

We give two combinatorial proofs of a product formula for the number of spanning trees of the $n$-dimensional hypercube. The first proof is based on the assertion that if one chooses a uniformly random rooted spanning tree of the hypercube and orient each edge from parent to child, then the parallel edges of the hypercube get orientations which are independent of one another. This independence property actually holds in a more general context and has intriguing consequences. The second proof uses some "killing involutions'' in order to identify the factors in the product formula. It leads to an enumerative formula for the spanning trees of the $n$-dimensional hypercube augmented with diagonals edges, counted according to the number of edges of each type. We also discuss more general formulas, obtained using a matrix-tree approach, for the number of spanning trees of the Cartesian product of complete graphs.
DOI : 10.37236/2510
Classification : 05A15, 05A19, 05C05, 05C30, 05C76, 05C65
Mots-clés : product formula, enumeration, number of spanning trees, hypercube, independence property, identification of factors

Olivier Bernardi  1

1 Brandeis University 
@article{10_37236_2510,
     author = {Olivier Bernardi},
     title = {On the spanning trees of the hypercube and other products of graphs},
     journal = {The electronic journal of combinatorics},
     year = {2012},
     volume = {19},
     number = {4},
     doi = {10.37236/2510},
     zbl = {1267.05020},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/2510/}
}
TY  - JOUR
AU  - Olivier Bernardi
TI  - On the spanning trees of the hypercube and other products of graphs
JO  - The electronic journal of combinatorics
PY  - 2012
VL  - 19
IS  - 4
UR  - http://geodesic.mathdoc.fr/articles/10.37236/2510/
DO  - 10.37236/2510
ID  - 10_37236_2510
ER  - 
%0 Journal Article
%A Olivier Bernardi
%T On the spanning trees of the hypercube and other products of graphs
%J The electronic journal of combinatorics
%D 2012
%V 19
%N 4
%U http://geodesic.mathdoc.fr/articles/10.37236/2510/
%R 10.37236/2510
%F 10_37236_2510
Olivier Bernardi. On the spanning trees of the hypercube and other products of graphs. The electronic journal of combinatorics, Tome 19 (2012) no. 4. doi: 10.37236/2510

Cité par Sources :