Counting graphs with different numbers of spanning trees through the counting of prime partitions

Title:

Counting graphs with different numbers of spanning trees through the counting of prime partitions

Creator:

Azarija, Jernej

Identifier:

https://cdk.lib.cas.cz/client/handle/uuid:4014b951-2a6d-48f6-b4e2-1121263560bf
uuid:4014b951-2a6d-48f6-b4e2-1121263560bf

Subject:

number of spanning trees, asymptotic, and prime partition

Type:

model:article and TEXT

Format:

bez média and svazek

Description:

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.

Language:

English

Rights:

http://creativecommons.org/publicdomain/mark/1.0/
policy:public

Coverage:

31-35

Source:

Czechoslovak Mathematical Journal | 2014 Volume:64 | Number:1

Harvested from:

CDK

Metadata only:

false