Richard Suchenwirth - In Graph theory in Tcl, a procedure was given how to compute the degree (the number of neighboring vertices) for a vertex of a graph. A graph can be characterized by his degree sequence, a non-increasing sequence of the degrees of the graph's vertices (see http://web.hamline.edu/~lcopes/SciMathMN/concepts/cdegsq.html ), which may look like
4,4,3,3,2,2,1,1,1,1
As this is ordered, it can equivalently be expressed as another sequence (for now, call it the "degree histogram")
h = (g0, g1, ... gm) where gi = card({v e V | g(v) = i})in other words, the number of vertices of each degree from 0 (singleton vertices) to the maximum degree occurring in that graph. Some examples:
(above) 0 4 2 2 2 K5 : 0 0 0 0 0 5 K3,3 : 0 0 0 6
A 5-legged star is 0 5 0 0 0 1, with the nice property that
g card(E)=1 and g1 = card(E)
A complete graph, where every vertex is connected with each, like K5 above, satisfies
gi = card(E) when i=card(E); otherwise 0
A 2-regular graph ("ring") with n vertices has the histogram
0 0 n
The number of vertices of the graph can be had by summing the histogram entries:
|V| = sum(i=0,m) gi
and the number of edges by multiplying the histogram entries with their position in the list, finally dividing by two:
|E| = sum(i=0,m) i gi/2
What that is good for? I experience with simple graphs that their degree histogram is a kind of "fingerprint", so graphs with same degree histogram are isomorphic. I am told that this is not to be expected to be true for every case. I wonder where the boundary is, i.e. which is the smallest pair of non-isomorphic graphs that share the same fingerprint. I somehow feel that the abstraction of degree histograms can be of use e.g. in determining whether a graph is planar.