Minimal graphs with a prescribed number of spanning trees

Importance: Medium ✭✭
Subject: Graph Theory
Recomm. for undergrads: yes
Posted by: azi
on: April 22nd, 2012

\begin{conjecture} Let $n \geq 3$ be an integer and let $\alpha(n)$ denote the least integer $k$ such that there exists a simple graph on $k$ vertices having precisely $n$ spanning trees. Then $ \alpha(n) = o(\log{n}).$ \end{conjecture}

% You may use many features of TeX, such as % arbitrary math (between $...$ and $$...$$) % \begin{theorem}...\end{theorem} environment, also works for question, problem, conjecture, ... % % Our special features: % Links to wikipedia: \Def {mathematics} or \Def[coloring]{Graph_coloring} % General web links: \href [The On-Line Encyclopedia of Integer Sequences]{} Observe that $\alpha(n)$ is well defined for $n \geq 3$ since $C_n$ has $n$ spanning trees.

The function was introduced by Sedlacek \cite{S} who has shown that for large enough $n$ $\alpha(n) \leq \frac{n+6}{3} \mbox{if } n \equiv 0 \pmod{3}$ and $\alpha(n) \leq \frac{n+4}{3} \mbox{if } n \equiv 2 \pmod{3}.$

Using the fact that almost all positive integers $n$ are expressible as $n = ab+ac+bc$ for integers $0 < a < b < c$ it can be shown \cite{A} that for large enough $n$

$ \alpha(n) \leq \frac{n+4}{3} \mbox{if } n \equiv 2 \pmod{3} $ and $\alpha(n) \leq \frac{n+9}{4} $ otherwise.

Moreover, the only fixed points of $\alpha$ are 3, 4, 5, 6, 7, 10, 13 and 22.

The conjecture is motivated by the following graph (ploted for a very small sample of vertices)


The conjecture \cite{C} is justifiable for highly composite numbers $n$ since in this case one can construct the graph obtained after taking cycles $C_{p_1}, \ldots,C_{p_k}$ for every odd prime factor $p_i$ of $n$.


% Example: %*[B] Claude Berge, Farbung von Graphen, deren samtliche bzw. deren ungerade Kreise starr sind, Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe 10 (1961), 114. % %[CRS] Maria Chudnovsky, Neil Robertson, Paul Seymour, Robin Thomas: \arxiv[The strong perfect graph theorem]{math.CO/0212070}, % Ann. of Math. (2) 164 (2006), no. 1, 51--229. \MRhref{MR2233847} % % (Put an empty line between individual entries) [S] J. Sedlacek, On the minimal graph with a given number of spanning trees, Canad. Math. Bull. 13 (1970) 515-517.

[A] J. Azarija, R. Skrekovski, Euler's idoneal numbers and an inequality concerning minimal graphs with a prescribed number of spanning trees, IMFM preprints 49 (2011) \href[Link to paper]{}

* [C] \href[Minimal graphs with a prescribed number of spanning trees]{}

* indicates original appearance(s) of problem.