Geodesic
Euler's idoneal numbers and an inequality concerning minimal graphs with a prescribed number of spanning trees
Mathematica Bohemica, Tome 138 (2013) no. 2, pp. 121-131

Voir la notice de l'article provenant de la source Czech Digital Mathematics Library

MR Zbl
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.
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.
DOI : 10.21136/MB.2013.143285
Classification : 05C05, 05C30, 05C35
Keywords: number of spanning trees; extremal graph 
Azarija, Jernej; Škrekovski, Riste. Euler's idoneal numbers and an inequality concerning minimal graphs with a prescribed number of spanning trees. Mathematica Bohemica, Tome 138 (2013) no. 2, pp. 121-131. doi: 10.21136/MB.2013.143285
@article{10_21136_MB_2013_143285,
     author = {Azarija, Jernej and \v{S}krekovski, Riste},
     title = {Euler's idoneal numbers and an inequality concerning minimal graphs with a prescribed number of spanning trees},
     journal = {Mathematica Bohemica},
     pages = {121--131},
     year = {2013},
     volume = {138},
     number = {2},
     doi = {10.21136/MB.2013.143285},
     mrnumber = {3099303},
     zbl = {06221243},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.21136/MB.2013.143285/}
}
TY  - JOUR
AU  - Azarija, Jernej
AU  - Škrekovski, Riste
TI  - Euler's idoneal numbers and an inequality concerning minimal graphs with a prescribed number of spanning trees
JO  - Mathematica Bohemica
PY  - 2013
SP  - 121
EP  - 131
VL  - 138
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.21136/MB.2013.143285/
DO  - 10.21136/MB.2013.143285
LA  - en
ID  - 10_21136_MB_2013_143285
ER  - 
%0 Journal Article
%A Azarija, Jernej
%A Škrekovski, Riste
%T Euler's idoneal numbers and an inequality concerning minimal graphs with a prescribed number of spanning trees
%J Mathematica Bohemica
%D 2013
%P 121-131
%V 138
%N 2
%U http://geodesic.mathdoc.fr/articles/10.21136/MB.2013.143285/
%R 10.21136/MB.2013.143285
%G en
%F 10_21136_MB_2013_143285

[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

[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 | Zbl

[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 | Zbl

[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 | MR | Zbl

[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 | Zbl

[9] Weil, A.: Number Theory: An Approach Through History from Hammurapi to Legendre. Birkhäuser, Boston (1984). | MR | Zbl

[10] Weinberger, P.: Exponents of class groups of complex quadratic fields. Acta Arith. 22 (1973), 117-124. | DOI | MR | Zbl

[11] Wesstein, E. W.: Idoneal Number. MathWorld---A Wolfram Web Resource, http:// mathworld.wolfram.com/IdonealNumber.html.

Cité par Sources :