Advanced Search

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

Let $A_n$ $(n\ge 1)$ be the set of all integers $x$ such that there exists a connected graph on $n$ vertices with precisely $x$ spanning trees. It was shown by Sedláček that $|A_n|$ grows faster than the linear function. In this paper, we show that $|A_n|$ grows faster than $\sqrt{n}{\mathrm{e}}^{(2\pi /\sqrt{3})\sqrt{n/logn}}$ by making use of some asymptotic results for prime partitions. The result settles a question posed in J. Sedláček, On the number of spanning trees of finite graphs, Čas. Pěst. Mat., 94 (1969), 217–221.

Let $\alpha \left(n\right)$ be the least number $k$ for which there exists a simple graph with $k$ vertices having precisely $n\ge 3$ spanning trees. Similarly, define $\beta \left(n\right)$ as the least number $k$ for which there exists a simple graph with $k$ edges having precisely $n\ge 3$ spanning trees. As an $n$-cycle has exactly $n$ spanning trees, it follows that $\alpha \left(n\right),\beta \left(n\right)\le n$. In this paper, we show that $\alpha \left(n\right)\le \frac{1}{3}(n+4)$ and $\beta \left(n\right)\le \frac{1}{3}(n+7)$ if and only if $n\notin \{3,4,5,6,7,9,10,13,18,22\}$, which is a subset of Euler’s idoneal numbers. Moreover, if $n\neg \equiv 2(mod3)$ and $n\ne 25$ we show that $\alpha \left(n\right)\le \frac{1}{4}(n+9)$ and $\beta \left(n\right)\le \frac{1}{4}(n+13).$ This improves some previously estabilished bounds.