IMFM
Institute of Mathematics, Physics and Mechanics Jadranska 19, 1000 Ljubljana, Slovenia
Preprint series Vol. 50 (2012), 1178
ISSN 2232-2094
COUNTING GRAPHS WITH DIFFERENT NUMBERS OF
SPANNING TREES THROUGH THE COUNTING OF PRIME PARTITIONS
Jernej Azarija
Ljubljana, June 28, 2012

00 CD
G
co
Counting graphs with different numbers of spanning trees through the counting of prime partitions
Jernej Azarija *
Abstract
Let An (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
|An| grows faster than y/ne	a question of Sedlacek posed
in [6].
£
1 Introduction
J. Sedlacek is regarded as one of the pioneers of Czech graph theory. He devoted much of his work to the study of subjects related to the number of spanning trees t(G) of a graph G. In [7] he studied the function a(n) defined as the least number k for which there exists a graph on k vertices having precisely n spanning trees. He showed that for every n > 6, it holds:
8	a(n) < f ^ if n = 0 (mod 3),
£
a(n) < ^ n±4 if n = 2 (mod 3). Azarija and Skrekovski [1] later found out that if n > 25 then:
a(n) < I ^ if n = 2 (mod 3), a(n) _ | «+9 otherwise.
Sedlacek continued to study quantities related to the function t. In [6] and [8] he considered the set B« defined as the set of integers so that x e B« whenever there is a t-regular graph on n vertices with precisely x spanning trees. He showed that for odd integers t > 3,	| | = ro and whenever t > 4 is an even integer
|Ba | = ro. In [6] he also studied a more general set - An defined as a set of numbers such that x E An whenever there exists a connected graph on n vertices having precisely x spanning trees. One could think about |An| as the maximal number of connected graphs on n vertices with mutually different numbers of spanning trees. Using a simple construction, he has shown that:
V |An| lim -= ro
n ^^o n
*Department of Mathematics, University of Ljubljana, Jadranska 21, 1000 Ljubljana, Slovenia, e-mail: jernej.azarija@gmail.com
and remarked: it is not clear how the fraction ^^ behaves when n tends to infinity. In modern terminology, we could write his result as |An| = u(n) since f (n) = u(g(n)) whenever |f (n)| > c|g(n)| for every c > 0 and n > n0 for an appropriately chosen n0.
In this paper, we extend his work and show that |An| = u(^neJ3^n/logn). In order to prove the result we define the graph CXl,...,Xk as follows. Let 3 < x1 < ■ ■ ■ < xk be integers. By Cxi Xk we denote the graph that is obtained after identifying a vertex 00 from the disjoint cycles CX1,..., CXk. Since CX1,..., CXk are the blocks of CXl,...,Xk, it follows that
CD
k k
T (CXi,...,Xk	Xi and |V (CXi,...,Xk )| = x% - k + 1.
i= 1 i= 1
We also introduce some number theoretical concepts. We say that (x1,...,xk) is a partition of n with integer parts 1 < x1 < ■ ■ ■ < xk if Y1 k=1 x% = n. The study of partitions covers an extensive part of the research done in combinatorics and number theory. If we denote by p(n) the number of partitions of n then, the celebrated theorem of Hardy and Ramanujan [3] states that
( )	1 n
p(n) ~ W3e
o
csr
CM
or, equivalently
lim P(n)' = 1.
rm
1 _eny -g-
4nV3
CO Since then, asymptotics for many types of partition functions have been studied [2].
For the interest of our paper is the function pp(n) which we define as the number of partitions of n into prime parts. In [5] Roth and Szekeres presented a theorem which can be used to derive the following asymptotic relation for pp
CO
Pp(n) - eTlv/n^.
Somehow surprising is the fact that if we disallow a constant number of primes as parts, the same asymptotic relation still holds. More specifically, if Pop(n) is the number of partitions into odd primes then
Pop(n) - Pp(n).
CD
2 Main Result
CD	_
In this section we prove that |An| =	logn) by showing that
1 •	1 An1
lim --= to.
vg^/log n
CD
We do so by estabilishing a lower bound for the number of partitions whose parts are only odd primes and whose sum is less than or equal to a given number n.

CSF

Lemma 1. Let Pn be the set of all partitions {x\,..., xk) withYli=i x% < n and all the numbers x1,... ,xk being odd primes. Then, there exists a n0 such that for all n > n0
iPni > 1 ymogn 73 ^n71ogn.
Proof. Let n be such a positive integer so that for all n > n
/ W 1 ^ Vn/ log n Pop(n) > ^e7 g .
For n > ni we then have
n	1 n	rn
|Pn| = EPop(i) > 1 E e21 ^ > 2	e^	dx.
00 2 2
Showing that J^_1 e ^^x/logx dx ~ f Vn log ne vn Vn/logn would imply the existence of a positive integer n2 such that
e^v7^7^ dx > 1 vmogne73 V"710^
Jni-1	2
for all n > n2. The statement of the theorem would then immediately follow for all n > n0 where n0 = max{n1, n2}. To prove the last asymptotic identity we observe that it follows from L'Hospital's rule that
i w _
lim Jni_1--= lim
n 1 e ^v^7^ dx	e 73
Jni—1	T	°
™ fvniogne™ dn(^vniogne^V7™^
Lemma 1 readily gives an asymptotic lower bound for |An|.
CO	_
Theorem 2. |An| = ^(^eT3Vn/logn).
Proof. Let Pn be defined in the same way as in the statement of Lemma 1. To every partition (x1,..., xk) G Pn with sum s = k=1 Xj we associate the graph obtained after identifying a vertex from Cxi,...,xk with a vertex from the disjoint path Pn_s+k. Observe that the resulting graph has precisely n vertices and k=1 x» spanning trees. Since all the parts in the partitions are primes it follows that any pair of graphs that were obtained from two different partitions in Pn have a different number of spanning trees. Thus
|An| > |Pn|
and therefore from Lemma 1 we know that for large enough n +J	_
lAni >1 vmogn ^V7™^ .
Since
1 m- /V log n
n. ^Vn log ne v^v 7 g
lim

yjnf log n
oo
it follows from the squeeze theorem that

00 CD
00 IN
lim —
ra^TO I— Vt /n/ logi y/ne v^v 1 g
oo
from where the stated claim follows.
□
Observe, that all the graphs constructed in the proof of Theorem 2 contain a cut vertex. Since almost all graphs are 2-connected [4] it is reasonable to expect that there exists a construction of a class Cn of 2-connected graphs of order n with mutually different number of spanning trees such that |Cn| = u(\Pn\). We thus leave it as a further investigation to try to improve the bound on the growth rate of \An\.
3 Acknowledgements
The author is thankful to Riste Skrekovski and Martin Raic for fruitful discussions.
0 o
1
CO
£ CO CO
CO CD
$H
CD CO
References
[1]	J. Azarija, R. Skrekovski, Euler's idoneal numbers and an inequality concerning minimal graphs with a prescribed number of spanning trees, manuscript, 2011.
[2]	P. Flajolet, R. Sedgewick, Analytic Combinatorics, Cambridge University Press 2009, p. 574.
[3]	G. H. Hardy, S. Ramanujan, Asymptotic formule in combinatory analysis, Proc. London Math. Soc. (2) 17 (1918)75-115.
[4]	F. Harary, E.M Palmer, Graphical Enumeration Academic Press, New York, 1973.
[5]	K. F. Roth, G. Szekeres, Some asymptotic formulae in the theory of partitions, Quarterly Journal of Mathematics, Oxford Series 5 (1954) 241-259.
[6]	J. Sedlacek, On the number of spanning trees of finite graphs, Cas. Pro. Pest Mat., Vol. 94 (1969) 217-221.
[7]	J. Sedlacek, On the minimal graph with a given number of spanning trees, Canad. Math. Bull. 13 (1970) 515-517.
[8]	J. Sedlacek, Regular graphs and their spanning trees, Cas. Pro. Pest Mat., Vol. 95 (1970) 420-426.
U
a
CD U