Counting graphs with different numbers of spanning trees through the counting of prime partitions. (English) Zbl 1340.05006

Azarija, Jernej

Czech. Math. J. 64, No. 1, 31-35 (2014).

Summary: Let \(A_n\) \((n \geq 1)\) be the set of all integers \(x\) such that there exists a connected graph on \(n\) vertices with precisely \(x\) spanning trees. It was shown by J. Sedláček [Čas. Pěst. Mat. 94, 217–221 (1969; Zbl 0175.20902)] that \(| A_n| \) grows faster than the linear function. In this paper, we show that \(| A_{n}| \) grows faster than \(\sqrt {n}\,{\text{e}}^{({2\pi}/{\sqrt 3})\sqrt {n/\log {n}}}\) by making use of some asymptotic results for prime partitions. The result settles a question posed in [loc. cit.].

MSC:

05A16	Asymptotic enumeration
05C35	Extremal problems in graph theory

Keywords:

number of spanning trees; asymptotic; prime partition

Citations:

Zbl 0175.20902

References:

[1]	J. Azarija, R. Škrekovski: Euler’s idoneal numbers and an inequality concerning minimal graphs with a prescribed number of spanning trees. Math. Bohem. 138 (2013), 121–131. · Zbl 1289.05043
[2]	P. Flajolet, R. Sedgewick: Analytic Combinatorics. Cambridge University Press, Cambridge, 2009.
[3]	F. Harary, E. M. Palmer: Graphical Enumeration. Academic Press, New York, 1973. · Zbl 0266.05108
[4]	G. H. Hardy, S. Ramanujan: Asymptotic formulae in combinatory analysis. Proc. London Math. Soc. 17 (1917), 75–115. · JFM 46.0198.04
[5]	K. F. Roth, G. Szekeres: Some asymptotic formulae in the theory of partitions. Q. J. Math., Oxf. II. Ser. 5 (1954), 241–259. · Zbl 0057.03902 · doi:10.1093/qmath/5.1.241
[6]	J. Sedláček: On the number of spanning trees of finite graphs. Čas. Pěst. Mat. 94 (1969), 217–221.
[7]	J. Sedláček: On the minimal graph with a given number of spanning trees. Can. Math. Bull. 13 (1970), 515–517. · Zbl 0202.23501 · doi:10.4153/CMB-1970-093-0
[8]	J. Sedláček: Regular graphs and their spanning trees. Čas. Pěst. Mat. 95 (1970), 402–426.