Previous |  Up |  Next


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:
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,
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://


Files Size Format View
MathBohem_138-2013-2_2.pdf 239.3Kb application/pdf View/Open
Back to standard record
Partner of
EuDML logo