Jernej Azarija, Riste Škrekovski, Department of Mathematics, University of Ljubljana, Jadranska 21, 1000 Ljubljana, Slovenia, e-mail: jernej.azarija@ gmail.com, skrekovski@gmail.com
Abstract: Let $\alpha(n)$ be the least number $k$ for which there exists a simple graph with $k$ vertices having precisely $n \geq3$ spanning trees. Similarly, define $\beta(n)$ as the least number $k$ for which there exists a simple graph with $k$ edges having precisely $n \geq3$ 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\frac13(n+4)$ and $\beta(n) \leq\frac13(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\equiv2 \pmod3$ and $n \not= 25$ we show that $\alpha(n) \leq\frac14(n+9)$ and $\beta(n) \leq\frac14(n+13).$ This improves some previously estabilished bounds.
Keywords: number of spanning trees, extremal graph
Classification (MSC 2010): 05C35, 05C05
Full text available as PDF.
Access to the full text of journal articles on this site is restricted to the subscribers of Myris Trade. To activate your access, please contact Myris Trade at myris@myris.cz.
