Geodesic
Counting graphs with different numbers of spanning trees through the counting of prime partitions
Czechoslovak Mathematical Journal, Tome 64 (2014) no. 1, pp. 31-35 Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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.
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.
DOI : 10.1007/s10587-014-0079-8
Classification : 05A16, 05C35
Keywords: number of spanning trees; asymptotic; prime partition 
@article{10_1007_s10587_014_0079_8,
     author = {Azarija, Jernej},
     title = {Counting graphs with different numbers of spanning trees through the counting of prime partitions},
     journal = {Czechoslovak Mathematical Journal},
     pages = {31--35},
     year = {2014},
     volume = {64},
     number = {1},
     doi = {10.1007/s10587-014-0079-8},
     mrnumber = {3247440},
     zbl = {06391472},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1007/s10587-014-0079-8/}
}
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
SP  - 31
EP  - 35
VL  - 64
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.1007/s10587-014-0079-8/
DO  - 10.1007/s10587-014-0079-8
LA  - en
ID  - 10_1007_s10587_014_0079_8
ER  - 
%0 Journal Article
%A Azarija, Jernej
%T Counting graphs with different numbers of spanning trees through the counting of prime partitions
%J Czechoslovak Mathematical Journal
%D 2014
%P 31-35
%V 64
%N 1
%U http://geodesic.mathdoc.fr/articles/10.1007/s10587-014-0079-8/
%R 10.1007/s10587-014-0079-8
%G en
%F 10_1007_s10587_014_0079_8
Azarija, Jernej. Counting graphs with different numbers of spanning trees through the counting of prime partitions. Czechoslovak Mathematical Journal, Tome 64 (2014) no. 1, pp. 31-35. doi: 10.1007/s10587-014-0079-8

[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 | Zbl

[2] Flajolet, P., Sedgewick, R.: Analytic Combinatorics. Cambridge University Press Cambridge (2009). | MR | Zbl

[3] Harary, F., Palmer, E. M.: Graphical Enumeration. Academic Press New York (1973). | MR | Zbl

[4] Hardy, G. H., Ramanujan, S.: Asymptotic formulae in combinatory analysis. Proc. London Math. Soc. 17 (1917), 75-115. | MR

[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 | MR | Zbl

[6] Sedláček, J.: On the number of spanning trees of finite graphs. Čas. Pěst. Mat. 94 (1969), 217-221. | MR | Zbl

[7] Sedláček, J.: On the minimal graph with a given number of spanning trees. Can. Math. Bull. 13 (1970), 515-517. | DOI | MR | Zbl

[8] Sedláček, J.: Regular graphs and their spanning trees. Čas. Pěst. Mat. 95 (1970), 402-426. | MR | Zbl

Cité par Sources :