| Title:
|
Counting graphs with different numbers of spanning trees through the counting of prime partitions (English) |
| Author:
|
Azarija, Jernej |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
64 |
| Issue:
|
1 |
| Year:
|
2014 |
| Pages:
|
31-35 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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. (English) |
| Keyword:
|
number of spanning trees |
| Keyword:
|
asymptotic |
| Keyword:
|
prime partition |
| MSC:
|
05A16 |
| MSC:
|
05C35 |
| idZBL:
|
Zbl 06391472 |
| idMR:
|
MR3247440 |
| DOI:
|
10.1007/s10587-014-0079-8 |
| . |
| Date available:
|
2014-09-29T09:29:09Z |
| Last updated:
|
2020-07-03 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/143945 |
| . |
| Reference:
|
[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. Zbl 1289.05043, MR 3099303 |
| Reference:
|
[2] Flajolet, P., Sedgewick, R.: Analytic Combinatorics.Cambridge University Press Cambridge (2009). Zbl 1165.05001, MR 2483235 |
| Reference:
|
[3] Harary, F., Palmer, E. M.: Graphical Enumeration.Academic Press New York (1973). Zbl 0266.05108, MR 0357214 |
| Reference:
|
[4] Hardy, G. H., Ramanujan, S.: Asymptotic formulae in combinatory analysis.Proc. London Math. Soc. 17 (1917), 75-115. MR 1575586 |
| Reference:
|
[5] Roth, K. F., Szekeres, G.: Some asymptotic formulae in the theory of partitions.Q. J. Math., Oxf. II. Ser. 5 (1954), 241-259. Zbl 0057.03902, MR 0067913, 10.1093/qmath/5.1.241 |
| Reference:
|
[6] Sedláček, J.: On the number of spanning trees of finite graphs.Čas. Pěst. Mat. 94 (1969), 217-221. Zbl 0175.20902, MR 0250931 |
| Reference:
|
[7] Sedláček, J.: On the minimal graph with a given number of spanning trees.Can. Math. Bull. 13 (1970), 515-517. Zbl 0202.23501, MR 0272672, 10.4153/CMB-1970-093-0 |
| Reference:
|
[8] Sedláček, J.: Regular graphs and their spanning trees.Čas. Pěst. Mat. 95 (1970), 402-426. Zbl 0201.56902, MR 0282876 |
| . |
