Minimal graphs with a prescribed number of spanning trees. (English) Zbl 1490.05127

Stong, Richard

Australas. J. Comb. 82, Part 2, 182-196 (2022).

Summary: For \(n\geq 3\), let \(\alpha(n)\) denote the minimum number of vertices in a graph with exactly \(n\) spanning subtrees. This notion was introduced by J. Sedláček [Can. Math. Bull. 13, 515–517 (1970; Zbl 0202.23501)] and has been studied by J. Azarija and R. Škrekovski [Math. Bohem. 138, No. 2, 121–131 (2013; Zbl 1289.05043)] In particular, they have conjectured that \(\alpha(n)=o(\log n)\). This paper will prove a weak version of this conjecture: specifically we will show that \(\alpha(n)=O((\log n)^{3/2}/(\log\log n))\). This bound is substantially larger than the conjectured upper bound; it is at least in the same ballpark.

MSC:

05C35	Extremal problems in graph theory
05C05	Trees

Citations:

Zbl 0202.23501; Zbl 1289.05043

Software:

MathOverflow

References:

[1]	J. Azarjia and R. ˘Skrekovski, Euler’s idoneal numbers and an inequality concerning minimal graphs with a prescribed number of spanning trees,Math. Bohem., October 2012.
[2]	S. Lang, “Algebraic Number Theory”, Graduate Texts in Mathematics, SpringerVerlag, New York (1994). · Zbl 0811.11001
[3]	L. Nebesk´y, On the minimum number of vertices and edges in a graph with a given number of spanning trees,Casopis pro pestov´˘an´ı matematiky98 (1973), 95-97. · Zbl 0251.05120
[4]	Open Problem Garden, Minimal graphs with a prescribed number of spanning trees,http://garden.irmacs.sfu.ca/category/graph_theory, Accessed: 2022-01-04. · Zbl 0781.52005
[5]	J. Sedl´a˘cek, On the minimal graph with a given number of spanning trees,Canad. Math. Bull.13 (1970), 515-517. · Zbl 0202.23501
[6]	https://mathoverflow.net/questions/133410/hecke-equidistribution; Accessed: 2022-01-04.
[7]	https://mathoverflow.net/questions/65059/ does-the-quadratic-form-x2-7y2-represent-infinitely-many-primes-with-; Accessed: 2022-01-04