Article
Full entry |
PDF
(0.2 MB)
Feedback
PDF
(0.2 MB)
Feedback
Keywords:
number of spanning trees; asymptotic; prime partition
number of spanning trees; asymptotic; prime partition
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 Sedláček that $|A_n|$ grows faster than the linear function. In this paper, we show that $|A_{n}|$ grows faster than $\sqrt {n} {\rm 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 J. Sedláček, On the number of spanning trees of finite graphs, Čas. Pěst. Mat., 94 (1969), 217–221.
References:
[1] Azarija, J., Škrekovski, R.: Euler's idoneal numbers and an inequality concerning minimal graphs with a prescribed number of spanning trees. Math. Bohem. 121-131 (2013), 138. MR 3099303 | Zbl 1289.05043
[2] Flajolet, P., Sedgewick, R.: Analytic Combinatorics. Cambridge University Press Cambridge (2009). MR 2483235 | Zbl 1165.05001
[3] Harary, F., Palmer, E. M.: Graphical Enumeration. Academic Press New York (1973). MR 0357214 | Zbl 0266.05108
[4] Hardy, G. H., Ramanujan, S.: Asymptotic formulae in combinatory analysis. Proc. London Math. Soc. 17 (1917), 75-115. MR 1575586
[5] Roth, K. F., Szekeres, G.: Some asymptotic formulae in the theory of partitions. Q. J. Math., Oxf. II. Ser. 5 (1954), 241-259. DOI 10.1093/qmath/5.1.241 | MR 0067913 | Zbl 0057.03902
[6] Sedláček, J.: On the number of spanning trees of finite graphs. Čas. Pěst. Mat. 94 (1969), 217-221. MR 0250931 | Zbl 0175.20902
[7] Sedláček, J.: On the minimal graph with a given number of spanning trees. Can. Math. Bull. 13 (1970), 515-517. DOI 10.4153/CMB-1970-093-0 | MR 0272672 | Zbl 0202.23501
[8] Sedláček, J.: Regular graphs and their spanning trees. Čas. Pěst. Mat. 95 (1970), 402-426. MR 0282876 | Zbl 0201.56902
Search
Partner of
