# Article

 Title: Euler's idoneal numbers and an inequality concerning minimal graphs with a prescribed number of spanning trees (English) Author: Azarija, Jernej Author: Škrekovski, Riste Language: English Journal: Mathematica Bohemica ISSN: 0862-7959 Volume: 138 Issue: 2 Year: 2013 Pages: 121-131 Summary lang: English . Category: math . 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. (English) Keyword: number of spanning trees Keyword: extremal graph MSC: 05C05 MSC: 05C35 . Date available: 2013-05-27T14:20:22Z Last updated: 2014-07-07 Stable URL: http://hdl.handle.net/10338.dmlcz/143285 . Reference: [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 Reference: [2] Cayley, G. A.: A theorem on trees.Quart. J. Math. 23 (1889), 276-378. Reference: [3] Chowla, S.: An extension of Heilbronn's class number theorem.Quart. J. Math. 5 (1934), 304-307. Zbl 0011.01001, 10.1093/qmath/os-5.1.304 Reference: [4] Clark, P.: Private communication, http://mathoverflow.net/questions/20955/the-missing-euler-idoneal-numbers.. Reference: [5] Gauss, C. F.: Disquisitiones Arithmeticae.Translated from the Latin by A. A. Clarke, 1966, Springer, New York (1986), English. Zbl 0585.10001, MR 0837656 Reference: [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. Reference: [7] Sedláček, J.: On the minimal graph with a given number of spanning trees.Canad. Math. Bull. 13 (1970), 515-517. Zbl 0202.23501, MR 0272672, 10.4153/CMB-1970-093-0 Reference: [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. Zbl 0251.05120, MR 0317998 Reference: [9] Weil, A.: Number Theory: An Approach Through History from Hammurapi to Legendre.Birkhäuser, Boston (1984). Zbl 0531.10001, MR 0734177 Reference: [10] Weinberger, P.: Exponents of class groups of complex quadratic fields.Acta Arith. 22 (1973), 117-124. Zbl 0217.04202, MR 0313221 Reference: [11] Wesstein, E. W.: Idoneal Number.MathWorld---A Wolfram Web Resource, http:// mathworld.wolfram.com/IdonealNumber.html. .

## Files

Files Size Format View
MathBohem_138-2013-2_2.pdf 239.3Kb application/pdf View/Open

Partner of