Geodesic
Note: Sharp Upper and Lower Bounds on the Number of Spanning Trees in Cartesian Product of Graphs
Discussiones Mathematicae. Graph Theory, Tome 33 (2013) no. 4, pp. 785-790

Voir la notice de l'article provenant de la source Library of Science

Let G_1 and G_2 be simple graphs and let n_1 = |V (G_1)|, m_1 = |E(G_1)| , n_2 = |V (G_2)| and m_2 = |E(G_2)|. In this paper we derive sharp upper and lower bounds for the number of spanning trees τ in the Cartesian product G_1 □ G_2 of G_1 and G_2. We show that: τ (G_1 □ G_2 ) ≥2(n_1-1)(n_2-1)/n_1 n_2 (τ (G_1) n_1 )^n_2+1/2 (τ(G_2)n_2)^n_1+1/2and τ(G_1 □ G_2 ) ≤τ (G_1) τ (G_2) [ 2m_1/n_1-1 + 2m_2/n_2-1]^(n_1 - 1)(n_2 -1) . We also characterize the graphs for which equality holds. As a by-product we derive a formula for the number of spanning trees in K_n_1□ K_n_2 which turns out to be n_1^n_1-2 n_2^n_2-2 (n_1 + n_2 )^(n_1-1)(n_2-1).
Keywords: Cartesian product graphs, spanning trees, number of spanning trees, inequality 
@article{DMGT_2013_33_4_a12,
     author = {Azarija, Jernej},
     title = {Note: {Sharp} {Upper} and {Lower} {Bounds} on the {Number} of {Spanning} {Trees} in {Cartesian} {Product} of {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {785--790},
     publisher = {mathdoc},
     volume = {33},
     number = {4},
     year = {2013},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2013_33_4_a12/}
}
TY  - JOUR
AU  - Azarija, Jernej
TI  - Note: Sharp Upper and Lower Bounds on the Number of Spanning Trees in Cartesian Product of Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2013
SP  - 785
EP  - 790
VL  - 33
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2013_33_4_a12/
LA  - en
ID  - DMGT_2013_33_4_a12
ER  - 
%0 Journal Article
%A Azarija, Jernej
%T Note: Sharp Upper and Lower Bounds on the Number of Spanning Trees in Cartesian Product of Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2013
%P 785-790
%V 33
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2013_33_4_a12/
%G en
%F DMGT_2013_33_4_a12
Azarija, Jernej. Note: Sharp Upper and Lower Bounds on the Number of Spanning Trees in Cartesian Product of Graphs. Discussiones Mathematicae. Graph Theory, Tome 33 (2013) no. 4, pp. 785-790. http://geodesic.mathdoc.fr/item/DMGT_2013_33_4_a12/