# Note: Sharp Upper and Lower Bounds on the Number of Spanning Trees in Cartesian Product of Graphs

• Volume: 33, Issue: 4, page 785-790
• ISSN: 2083-5892

top

## Abstract

top
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: [...] and [...] . 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 [...] .

## How to cite

top

Jernej Azarija. "Note: Sharp Upper and Lower Bounds on the Number of Spanning Trees in Cartesian Product of Graphs." Discussiones Mathematicae Graph Theory 33.4 (2013): 785-790. <http://eudml.org/doc/268315>.

@article{JernejAzarija2013,
abstract = {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: [...] and [...] . 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 [...] .},
author = {Jernej Azarija},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {Cartesian product graphs; spanning trees; number of spanning trees; inequality},
language = {eng},
number = {4},
pages = {785-790},
title = {Note: Sharp Upper and Lower Bounds on the Number of Spanning Trees in Cartesian Product of Graphs},
url = {http://eudml.org/doc/268315},
volume = {33},
year = {2013},
}

TY - JOUR
AU - Jernej Azarija
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
VL - 33
IS - 4
SP - 785
EP - 790
AB - 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: [...] and [...] . 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 [...] .
LA - eng
KW - Cartesian product graphs; spanning trees; number of spanning trees; inequality
UR - http://eudml.org/doc/268315
ER -

## References

top
1. [1] R.B. Bapat and S. Gupta, Resistance distance in wheels and fans, Indian J. Pure Appl. Math. 41 (2010) 1-13.[WoS] Zbl1203.05041
2. [2] Z. Bogdanowicz, Formulas for the number of spanning trees in a fan, Appl. Math. Sci. 16 (2008) 781-786. Zbl1166.05015
3. [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 Zbl0699.90041
4. [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[Crossref] Zbl0785.60007
5. [5] G.A. Cayley, A theorem on trees, Quart. J. Math 23 (1889) 276-378. doi:10.1017/CBO9780511703799.010[Crossref]
6. [6] M.H.S. Haghighi and K. Bibak, Recursive relations for the number of spanning trees, Appl. Math. Sci. 46 (2009) 2263-2269. Zbl1205.05050
7. [7] R. Hammack, W. Imrich and S. Klavžar, Handbook of Product Graphs, 2nd Edition (CRC press, 2011). Zbl1283.05001
8. [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[Crossref]
9. [9] B. Mohar, The laplacian spectrum of graphs, in: Graph Theory, Combinatorics, and Applications (Wiley, 1991). Zbl0840.05059
10. [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 [Crossref] Zbl0949.05041

## NotesEmbed?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.