Univ.Beograd.Publ.Elektrotehn.Fak.
Ser.Mat.13(2002),30–35.
THE V ARIANCE OF THE VERTEX DEGREES
OF RANDOMLY GENERATED GRAPHS
Ivan Gutman,Peter Paule
We consider graphs with n vertices and m edges constructed from n isolated
vertices by lecting among them,uniformly at random,m pairs and con-
necting them by m edges.The variance of the vertex degrees of such graphs
is shown to be equal to 2m (n 2−n −2m )/(n 3+n 2).In order to arrive at
this formula some combinatorial identities are verified.
1.INTRODUCTION
In connection with our recent studies of some spectral properties of randomly generated graphs [3,4]we encountered the problem of finding the expected value and the variance of the vertex degrees of such graphs.
A graph posssing n vertices and m edges will be referred to as an (n,m )-graph.The random (n,m )-graphs examined by us were constructed by starting with the (n,0)-graph,lecting in it,uniformly at random,m vertex pairs and connecting them by m edges.(This construction produces labelled (n,m )-graphs uniformly at random.)
One should note that under “random graph ”one usually understands a graph with a fixed number of vertices,in which there is a given probability that an edge exists between any two vertices [1].Hence the number of edges of such a random graph is a random variable [1].On the other hand,the graphs considered in this paper have a fixed number m of edges,and only the placement of the edges between vertices is chon by random.
Let G be a random (n,m )-graph,constructed as described above.Denote the number of its vertex pairs by N ;evidently N =n (n −1)/2.In view of the fact that m edges in G can be lected in N m distinct ways,and that the number of choices in which exactly k edges meet at a certain vertex
2000Mathematics Subject Classification:05C80,05A19
Keywords and Phras:Random graph,vertex degree variance,variance (of graph)
30
The variance of the vertex degrees of randomly generated graphs31
is
n−1
k
N−(n−1)
m−k
,the probability that a vertex in G has degree k is
(1)P(k|n,m)=
n−1
k
N−(n−1)
m−k
N
m
.
This,of cour,applies to any vertex of G.
The expected value E(d)of the degree of a vertex(any vertex)of G is thus
(2)E(d)=n−1
k=0
k P(k|n,m)
the expected value of the square of the respective degree is
(3)E(d2)=n−1
k=0
k2P(k|n,m)
and the variance
(4)Var(d)=E(d2)−E(d)2.
2.THE MAIN RESULTS
The average vertex degree in any(n,m)-graph is2m/n.Conquently E(d)= 2m/n,which,in view of Eqs.(1)and(2),is tantamount to
n−1
k=1k
n−1
k
(n−1)(n−2)/2
m−k
=
2m
n
n(n−1)/2
m
<,
(5)
n
k=1
k
n
k
n(n−1)/2
m−k
=
2m
n+1
n(n+1)/2
m
.
The above reasoning provides thus an elementary and utmost simple graph–
theory–bad proof of the combinatorial identity(5).
The next problem is tofind a similar expression for E(d2)in terms of the parameters n and m.This could be achieved by calculating the sum S2
S2=n−1
k=1
k2
n−1
k
(n−1)(n−2)/2
m−k
.
In what follows we show that
(6)S2=2m
n
·
2m+n−1
n+1
n(n−1)/2
m
.
32Ivan Gutman,Peter Paule
From this formula and Eqs.(3)and (4)it is immediate that
E (d 2)=
2m (2m +n −1)n (n +1)
and
(7)Var (d )=2m n (n −1)−2m n 2(n +1).3.PROOF OF FORMULA (6)
The expression (6)for S 2is deduced by using two elementary identities that are,for instance,found in Riordan ’s minal book [6],namely
(8) r k =r k r −1k −1
(k =0)and Vandermonde ’s formula
(9) k r k s n −k = r +s n
(n ≥0).
By repeated application of (8)and (9)we obtain
S 2=(n −1)n −2
k =0(k +1) n −2k (n −1)(n −2)/2m −1−k =(n −1)n −2 k =0k n −2k (n −1)(n −2)/2m −1−k +(n −1) (n −2)(n +1)/2m −1 =(n −1)(n −2)n −2 k =1 n −3k −1 (n −1)(n −2)/2m −1−k +(n −1) (n −2)(n +1)/2m −1 =(n −1)(n −2)n −3 k =0 n −3k (n −1)(n −2)/2m −2−k +(n −1) (n −2)(n +1)/2m −1 =(n −1)(n −2) n −3+(n −1)(n −2)/2m −2 +(n −1) (n −2)(n +1)/2m −1 =(n −1)(n −2)(m −1)n −2+(n −1)(n −2)/2 n −2+(n −1)(n −2)/2m −1 +(n −1) (n −2)(n +1)/2m −1 =(n −1) n −2+(n −1)(n −2)/2m −1 · (n −2)(m −1)(n −2)(1+(n −1)/2)+1
The variance of the vertex degrees of randomly generated graphs 33=(n −1) (n −2)(n +1)/2m −1 2(m −1)n +1+1 =(n −1)2m n (n −1) n (n −1)/2m 2m −2+n +1n +1
and Eq.(6)follows.
Thus we proved a combinatorial identity
(10)n
k =1k 2 n k n (n −1)/2m −k
=2m (2m +n )(n +1)(n +2) n (n +1)/2m .Remark.One can prove this also automatically by using Zeilberger ’s algorithm.We demonstrate this by using the Paule/Schorn package [5]:
In[1]:=<<zb.m
Fast Zeilberger by Peter Paule and Markus Schorn.(V 2.4test)Systembreaker =ENullspace
In[4]:=g =k^2Binomial[n-1,k]Binomial[(n-1)(n-2)/2,m-k]/
Binomial[n(n-1)/2,m]
2(-2+n)(-1+n)
k Binomial[-1+n,k]Binomial[-----------------,m -k]
2
Out[4]=---------------------------------------------------------
(-1+n)n
Binomial[----------,m]
2
In[5]:=Zb[g,{k,0,m},m,1]
If ‘m’is a natural number,then:
Out[5]={-((1+m)(-2+n)(1+2m +n)SUM[m])+
m (-2+n)(-1+2m +n)SUM[1+m]==0}
It is easy to verify that SUM (m )=2m (2m +n −1)/ n (n +1) satisfies the
recurrence.By checking that also the initial value of both quences in m is the same,we complete the proof of the evaluation.
More generally,the identities (5)and (10)are special instances of
n
k =1k r k s n −k
=n r r +s r +s n
34
Ivan Gutman,Peter Paule and n
k =1k 2 r k s n −k =n r r +s ·n (r −1)+s r −1+s r +s n
respectively.Also the variants of Vandermonde ’s formula can be easily obtained in the same automatic fashion.
4.DISCUSSION
Obrving that the complement G of the graph G posss m =n (n −1)/2−m edges,we can rewrite Eq.(7)as
(11)Var (d )=1n +1 2m n 2m n
.Clearly,2m/n and 2m/n are the average vertex degrees in G and G ,respectively.
The maximum value of Var (d )is achieved when m =m and is equal to (n −1)2/ 4(n +1) ∼n/4.
If m is much smaller than m (namely,when the graph G is spar),then Var (d )≈2m/n ,i.e.,
Var (d )≈E (d ).
In various graph–theoretical considerations we often encounter graphs that are said to be “almost regular”.Formula (11)provides now a measure of this “almost–regularity”:an (n,m )-graph may be viewed as “almost–regular”if the variance of its vertex degrees is sufficiently smaller than the right–hand side of
(11).
Finally,we wish to point out that in contemporary graph theory another problem related to the variance of the vertex degrees is much examined,namely the characterization of graphs in which this variance is large or the largest possible,e [2]and the references cited therein.This direction of rearch has,however,little in common with the prent work.
REFERENCES
1. B.Bollob ´a
s :Random Graphs.Academic Press,New York,1984.2.Y.Caro,R.Yuster :Graphs with large variance.Ars Combinatoria,57(2000),151–162.
3.I.Gutman,T.Soldatovi ´c
,D.Vidovi ´c :The energy of a graph and its size depen-dence.A Monte Carlo approach.Chem.Phys.Lett.,297(1998),428–432.
4.I.Gutman,T.Soldatovi ´c
,D.Vidovi ´c :Modeling the dependence of the π-electron energy on the size of conjugated molecules.A Monte Carlo approach.ACH Models in Chem.,136(1999),599–608.
The variance of the vertex degrees of randomly generated graphs35
5.P.Paule,M.Schorn:A Mathematica version of Zeilberger’s algorithm for proving
binomial coefficient identities.J.Symbolic Computation,20(1995),673–698.
6.J.Riordan:Combinatorial Identities.Wiley,New York,1968.
Faculty of Science,(Received March1,2000) University of Kragujevac,
P.O.Box60,
YU–34000Kragujevac,
Yugoslavia
Rearch Institute for Symbolic Computation,
Johannes Kepler University Linz,
A–4040Linz,
Austria
