Displaying similar documents to “Weighted spanning trees on some self-similar graphs.”

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

Jernej Azarija (2013)

Discussiones Mathematicae Graph Theory

Similarity:

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 [...] .