Note: Sharp Upper and Lower Bounds on the Number of Spanning Trees in Cartesian Product of Graphs
Discussiones Mathematicae Graph Theory (2013)
- Volume: 33, Issue: 4, page 785-790
- ISSN: 2083-5892
Access Full Article
top
Abstract
topHow to cite
topJernej 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] 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] Z. Bogdanowicz, Formulas for the number of spanning trees in a fan, Appl. Math. Sci. 16 (2008) 781-786. Zbl1166.05015
- [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] 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] G.A. Cayley, A theorem on trees, Quart. J. Math 23 (1889) 276-378. doi:10.1017/CBO9780511703799.010[Crossref]
- [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] R. Hammack, W. Imrich and S. Klavžar, Handbook of Product Graphs, 2nd Edition (CRC press, 2011). Zbl1283.05001
- [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] B. Mohar, The laplacian spectrum of graphs, in: Graph Theory, Combinatorics, and Applications (Wiley, 1991). Zbl0840.05059
- [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 ?
topYou 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.