Discussiones Mathematicae Graph Theory 33(4) (2013) 785-790
doi: 10.7151/dmgt.1698

[BIBTex] [PDF] [PS]

Sharp upper and lower bounds on the number of spanning trees in Cartesian product of graphs

Jernej Azarija

Department of Mathematics, University of Ljubljana
Jadranska 21,
1000 Ljubljana, Slovenia


Let G1 and G2 be simple graphs and let n1 = |V(G1) |, m1 = |E(G1) |, n2 = |V(G2) | and m2 = |E(G2) |. In this paper we derive sharp upper and lower bounds for the number of spanning trees τ in the Cartesian product G1◻G2 of G1 and G2. We show that:
τ(G1◻G2) ≥ 2(n1 −1)(n2 −1)/(n1n2) ( τ(G1) n1)(n2+1)/2) ( τ(G2)n2)(n1+1)/2
τ(G1◻G2) ≤ τ(G1) τ(G2) [ 2m1/(n1 −1) + 2m2/(n2 −1) ](n1 −1)(n2 −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 Kn1◻Kn2 which turns out to be n1n1 −2n2n2 −2(n1+n2)(n1 −1)(n2 −1).

Keywords: Cartesian product graphs, spanning trees, number of spanning trees, inequality

2010 Mathematics Subject Classification: 05C76.


[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, Über die Auflösung 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 .

Received 16 April 2012
Revised 29 September 2012
Accepted 1 October 2012