Article
Full entry |
PDF
(0.2 MB)
Feedback
PDF
(0.2 MB)
Feedback
Keywords:
number of spanning trees; extremal graph
number of spanning trees; extremal graph
Summary:
Let $\alpha (n)$ be the least number $k$ for which there exists a simple graph with $k$ vertices having precisely $n \geq 3$ spanning trees. Similarly, define $\beta (n)$ as the least number $k$ for which there exists a simple graph with $k$ edges having precisely $n \geq 3$ spanning trees. As an $n$-cycle has exactly $n$ spanning trees, it follows that $\alpha (n),\beta (n) \leq n$. In this paper, we show that $\alpha (n) \leq \frac 13(n+4)$ and $\beta (n) \leq \frac 13(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 \not \equiv 2 \pmod {3}$ and $n \not = 25$ we show that $\alpha (n) \leq \frac 14(n+9)$ and $\beta (n) \leq \frac 14(n+13).$ This improves some previously estabilished bounds.
References:
[1] Baron, G., Boesch, F., Prodinger, H., Tichy, R. F., Wang, J.: The number of spanning trees in the square of cycle. Fibonacci Q. 23 (1985), 258-264. MR 0806296
[2] Cayley, G. A.: A theorem on trees. Quart. J. Math. 23 (1889), 276-378.
[3] Chowla, S.: An extension of Heilbronn's class number theorem. Quart. J. Math. 5 (1934), 304-307. DOI 10.1093/qmath/os-5.1.304 | Zbl 0011.01001
[4] Clark, P.: Private communication, http://mathoverflow.net/questions/20955/the-missing-euler-idoneal-numbers</b>
[5] Gauss, C. F.: Disquisitiones Arithmeticae. Translated from the Latin by A. A. Clarke, 1966, Springer, New York (1986), English. MR 0837656 | Zbl 0585.10001
[6] Kirchhoff, G. G.: Über die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Verteilung galvanischer Ströme geführt wird. Ann. Phys. Chem. 72 (1847), 497-508.
[7] Sedláček, J.: On the minimal graph with a given number of spanning trees. Canad. Math. Bull. 13 (1970), 515-517. DOI 10.4153/CMB-1970-093-0 | MR 0272672 | Zbl 0202.23501
[8] Nebeský, L.: On the minimum number of vertices and edges in a graph with a given number of spanning trees. Čas. Pěst. Mat. 98 (1973), 95-97. MR 0317998 | Zbl 0251.05120
[9] Weil, A.: Number Theory: An Approach Through History from Hammurapi to Legendre. Birkhäuser, Boston (1984). MR 0734177 | Zbl 0531.10001
[10] Weinberger, P.: Exponents of class groups of complex quadratic fields. Acta Arith. 22 (1973), 117-124. DOI 10.4064/aa-22-2-117-124 | MR 0313221 | Zbl 0217.04202
[11] Wesstein, E. W.: Idoneal Number. MathWorld---A Wolfram Web Resource, http:// mathworld.wolfram.com/IdonealNumber.html.
Search
Partner of
