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/

[1] R.B. Bapat and S. Gupta, Resistance distance in wheels and fans, Indian J. Pure Appl. Math. 41 (2010) 1-13.

[2] Z. Bogdanowicz, Formulas for the number of spanning trees in a fan, Appl. Math. Sci. 16 (2008) 781-786.

[3] F.T. Boesch, On unreliabillity polynomials and graph connectivity in reliable network synthesis, J. Graph Theory 10 (1986) 339-352. doi:10.1002/jgt.3190100311

[4] R. Burton and R. Pemantle, Local characteristics, entropy and limit theorems for spanning trees and domino tilings via transfer-impedances, Ann. Probab. 21 (1993) 1329-1371. doi:10.1214/aop/1176989121

[5] G.A. Cayley, A theorem on trees, Quart. J. Math 23 (1889) 276-378. doi:10.1017/CBO9780511703799.010

[6] M.H.S. Haghighi and K. Bibak, Recursive relations for the number of spanning trees, Appl. Math. Sci. 46 (2009) 2263-2269.

[7] R. Hammack, W. Imrich and S. Klavžar, Handbook of Product Graphs, 2nd Edition (CRC press, 2011).

[8] G.G. Kirchhoff, ¨Uber die Aufl¨osung der Gleichungen, auf welche man bei der Untersuchung der linearen Verteilung galvanischer Strome gefhrt wird, Ann. Phy. Chem. 72 (1847) 497-508. doi:10.1002/andp.18471481202

[9] B. Mohar, The laplacian spectrum of graphs, in: Graph Theory, Combinatorics, and Applications (Wiley, 1991).

[10] R. Shrock and F.Y. Wu, Spanning trees on graphs and lattices in d dimensions, J. Phys. A 33 (2000) 3881-3902. doi:10.1088/0305-4470/33/21/303