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

Let A_n (n >= 1) be the set of all integers x such that there exists a connected graph on n vertices with precisely x spanning trees. In this paper, we show that |A_n| grows faster than sqrt{n}exp(2Pi*sqrt{n/log{n}/Sqrt(3)} This settles a question of Sedlacek.

Saved in:
Bibliographic Details
Published in:arXiv.org 2012-10
Main Author: Azarija, Jernej
Format: Article
Language:English
Subjects:
Apexes
Graph theory
Integers
Trees (mathematics)
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Let A_n (n >= 1) be the set of all integers x such that there exists a connected graph on n vertices with precisely x spanning trees. In this paper, we show that |A_n| grows faster than sqrt{n}exp(2Pi*sqrt{n/log{n}/Sqrt(3)} This settles a question of Sedlacek.
ISSN:2331-8422