PDF

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

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

Abstract

Let G₁ and G₂ be simple graphs and let n₁ = |V(G₁) |, m₁ = |E(G₁) |, n₂ = |V(G₂) | and m₂ = |E(G₂) |. In this paper we derive sharp upper and lower bounds for the number of spanning trees τ in the Cartesian product G₁◻G₂ of G₁ and G₂. We show that:

τ(G1◻G2) ≥ 2(n1 −1)(n2 −1)/(n1n2) ( τ(G1) n1)(n2+1)/2) ( τ(G2)n2)(n1+1)/2

and

τ(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 K_n1◻K_n2 which turns out to be n₁^{n₁ −2}n₂^{n₂ −2}(n₁+n₂)^{(n₁ −1)(n₂ −1)}.

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

2010 Mathematics Subject Classification: 05C76.

References

[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