Euler's idoneal numbers and an inequality concerning minimal graphs with a prescribed number of spanning trees

Jernej Azarija; Riste Škrekovski

Mathematica Bohemica (2013)

  • Volume: 138, Issue: 2, page 121-131
  • ISSN: 0862-7959

Abstract

top
Let α ( n ) be the least number k for which there exists a simple graph with k vertices having precisely n ≥ 3 spanning trees. Similarly, define β ( n ) as the least number k for which there exists a simple graph with k edges having precisely n ≥ 3 spanning trees. As an n -cycle has exactly n spanning trees, it follows that α ( n ) , β ( n ) ≤ n . In this paper, we show that α ( n ) ≤ 1 3 ( n + 4 ) and β ( n ) ≤ 1 3 ( n + 7 ) if and only if n ∉ { 3 , 4 , 5 , 6 , 7 , 9 , 10 , 13 , 18 , 22 } , which is a subset of Euler’s idoneal numbers. Moreover, if n ¬ ≡ 2 ( mod 3 ) and n ≠ 25 we show that α ( n ) ≤ 1 4 ( n + 9 ) and β ( n ) ≤ 1 4 ( n + 13 ) . This improves some previously estabilished bounds.

How to cite

top

Azarija, Jernej, and Škrekovski, Riste. "Euler's idoneal numbers and an inequality concerning minimal graphs with a prescribed number of spanning trees." Mathematica Bohemica 138.2 (2013): 121-131. <http://eudml.org/doc/252492>.

@article{Azarija2013,
abstract = {Let $\alpha (n)$ be the least number $k$ for which there exists a simple graph with $k$ vertices having precisely $n \ge 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 \ge 3$ spanning trees. As an $n$-cycle has exactly $n$ spanning trees, it follows that $\alpha (n),\beta (n) \le n$. In this paper, we show that $\alpha (n) \le \frac\{1\}\{3\}(n+4)$ and $\beta (n) \le \frac\{1\}\{3\}(n+7) $ if and only if $n \notin \lbrace 3,4,5,6,7,9,10,13,18,22\rbrace $, which is a subset of Euler’s idoneal numbers. Moreover, if $n \lnot \equiv 2 \hspace\{4.44443pt\}(\@mod \; 3)$ and $n \ne 25$ we show that $\alpha (n) \le \frac\{1\}\{4\}(n+9)$ and $\beta (n) \le \frac\{1\}\{4\}(n+13).$ This improves some previously estabilished bounds.},
author = {Azarija, Jernej, Škrekovski, Riste},
journal = {Mathematica Bohemica},
keywords = {number of spanning trees; extremal graph; spanning tree},
language = {eng},
number = {2},
pages = {121-131},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {Euler's idoneal numbers and an inequality concerning minimal graphs with a prescribed number of spanning trees},
url = {http://eudml.org/doc/252492},
volume = {138},
year = {2013},
}

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
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 138
IS - 2
SP - 121
EP - 131
AB - Let $\alpha (n)$ be the least number $k$ for which there exists a simple graph with $k$ vertices having precisely $n \ge 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 \ge 3$ spanning trees. As an $n$-cycle has exactly $n$ spanning trees, it follows that $\alpha (n),\beta (n) \le n$. In this paper, we show that $\alpha (n) \le \frac{1}{3}(n+4)$ and $\beta (n) \le \frac{1}{3}(n+7) $ if and only if $n \notin \lbrace 3,4,5,6,7,9,10,13,18,22\rbrace $, which is a subset of Euler’s idoneal numbers. Moreover, if $n \lnot \equiv 2 \hspace{4.44443pt}(\@mod \; 3)$ and $n \ne 25$ we show that $\alpha (n) \le \frac{1}{4}(n+9)$ and $\beta (n) \le \frac{1}{4}(n+13).$ This improves some previously estabilished bounds.
LA - eng
KW - number of spanning trees; extremal graph; spanning tree
UR - http://eudml.org/doc/252492
ER -

References

top
  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. (1985) MR0806296
  2. Cayley, G. A., A theorem on trees, Quart. J. Math. 23 (1889), 276-378. (1889) 
  3. Chowla, S., 10.1093/qmath/os-5.1.304, Quart. J. Math. 5 (1934), 304-307. (1934) Zbl0011.01001DOI10.1093/qmath/os-5.1.304
  4. Clark, P., Private communication, http://mathoverflow.net/questions/20955/the-missing-euler-idoneal-numbers, . 
  5. Gauss, C. F., Disquisitiones Arithmeticae, Translated from the Latin by A. A. Clarke, 1966, Springer, New York (1986), English. (1986) Zbl0585.10001MR0837656
  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. (1847) 
  7. Sedláček, J., 10.4153/CMB-1970-093-0, Canad. Math. Bull. 13 (1970), 515-517. (1970) Zbl0202.23501MR0272672DOI10.4153/CMB-1970-093-0
  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. (1973) Zbl0251.05120MR0317998
  9. Weil, A., Number Theory: An Approach Through History from Hammurapi to Legendre, Birkhäuser, Boston (1984). (1984) Zbl0531.10001MR0734177
  10. Weinberger, P., 10.4064/aa-22-2-117-124, Acta Arith. 22 (1973), 117-124. (1973) Zbl0217.04202MR0313221DOI10.4064/aa-22-2-117-124
  11. Wesstein, E. W., Idoneal Number, MathWorld---A Wolfram Web Resource, http:// mathworld.wolfram.com/IdonealNumber.html. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.