Counting graphs with different numbers of spanning trees through the counting of prime partitions
Czechoslovak Mathematical Journal (2014)
- Volume: 64, Issue: 1, page 31-35
- ISSN: 0011-4642
Access Full Article
top
Abstract
topHow to cite
topAzarija, Jernej. "Counting graphs with different numbers of spanning trees through the counting of prime partitions." Czechoslovak Mathematical Journal 64.1 (2014): 31-35. <http://eudml.org/doc/262047>.
@article{Azarija2014,
abstract = {Let $A_n$$(n \ge 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.},
author = {Azarija, Jernej},
journal = {Czechoslovak Mathematical Journal},
keywords = {number of spanning trees; asymptotic; prime partition; number of spanning trees; asymptotic; prime partition},
language = {eng},
number = {1},
pages = {31-35},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {Counting graphs with different numbers of spanning trees through the counting of prime partitions},
url = {http://eudml.org/doc/262047},
volume = {64},
year = {2014},
}
TY - JOUR
AU - Azarija, Jernej
TI - Counting graphs with different numbers of spanning trees through the counting of prime partitions
JO - Czechoslovak Mathematical Journal
PY - 2014
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 64
IS - 1
SP - 31
EP - 35
AB - Let $A_n$$(n \ge 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.
LA - eng
KW - number of spanning trees; asymptotic; prime partition; number of spanning trees; asymptotic; prime partition
UR - http://eudml.org/doc/262047
ER -
References
top- 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. (2013) Zbl1289.05043MR3099303
- Flajolet, P., Sedgewick, R., Analytic Combinatorics, Cambridge University Press Cambridge (2009). (2009) Zbl1165.05001MR2483235
- Harary, F., Palmer, E. M., Graphical Enumeration, Academic Press New York (1973). (1973) Zbl0266.05108MR0357214
- Hardy, G. H., Ramanujan, S., Asymptotic formulae in combinatory analysis, Proc. London Math. Soc. 17 (1917), 75-115. (1917) MR1575586
- Roth, K. F., Szekeres, G., 10.1093/qmath/5.1.241, Q. J. Math., Oxf. II. Ser. 5 (1954), 241-259. (1954) Zbl0057.03902MR0067913DOI10.1093/qmath/5.1.241
- Sedláček, J., On the number of spanning trees of finite graphs, Čas. Pěst. Mat. 94 (1969), 217-221. (1969) Zbl0175.20902MR0250931
- Sedláček, J., 10.4153/CMB-1970-093-0, Can. Math. Bull. 13 (1970), 515-517. (1970) Zbl0202.23501MR0272672DOI10.4153/CMB-1970-093-0
- Sedláček, J., Regular graphs and their spanning trees, Čas. Pěst. Mat. 95 (1970), 402-426. (1970) Zbl0201.56902MR0282876
NotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.