Open AccessThe variance of the vertex degrees of randomly generated graphs
Author(s) -
Iván Gutman,
Peter Paule
Publication year - 2002
Publication title -
publikacija elektrotehnickog fakulteta - serija matematika
Language(s) - English
Resource type - Journals
eISSN - 2406-0852
pISSN - 0353-8893
DOI - 10.2298/petf0213030g
Subject(s) - combinatorics , vertex (graph theory) , mathematics , variance (accounting) , random graph , graph , discrete mathematics , accounting , business
We consider graphs with n vertices and m edges constructed from n isolated vertices by selecting among them, uniformly at random, m pairs and connecting them by m edges. The variance of the vertex degrees of such graphs is shown to be equal to 2m (n - n − 2m)/(n 3+ n ) . In order to arrive at this formula some combinatorial identities are verified.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom