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

@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 -