| 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 (print) |
| ISSN:
|
2464-7136 (online) |
| 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:
|
05C30 |
| MSC:
|
05C35 |
| idZBL:
|
Zbl 06221243 |
| idMR:
|
MR3099303 |
| DOI:
|
10.21136/MB.2013.143285 |
| . |
| Date available:
|
2013-05-27T14:20:22Z |
| Last updated:
|
2020-07-29 |
| 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, 10.4064/aa-22-2-117-124 |
| Reference:
|
[11] Wesstein, E. W.: Idoneal Number.MathWorld---A Wolfram Web Resource, http:// mathworld.wolfram.com/IdonealNumber.html. |
| . |
