Article contents
The second moment of the complexity of a graph
Published online by Cambridge University Press: 26 February 2010
Extract
A graph consists of a set of vertices some pairs of which are joined by a single edge. A tree is a graph with the property that each pair of vertices is connected by precisely one path, i.e., a sequence of distinct vertices joined consecutively by edges. The complexity c of a graph G(n, k) with n vertices and k edges is the number of trees with n vertices which are subgraphs of G(n, k). The distribution of c over the class of all graphs G(n, k) is of physical interest because it throws light on the classical many-body problem. (See, e.g. [9].) Ford and Uhlenbeck [3] gave numerical data which suggested that the distribution of c tends to normality for increasing n if k is near No moments higher than the first were known in general and they remarked in [4] that even “the second would be worth knowing”. The main object in this paper is to derive a formula for the second moment of c.
- Type
- Research Article
- Information
- Copyright
- Copyright © University College London 1964
References
- 14
- Cited by