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 proc degreeSequence g { set res {} foreach node [nodes $g] { lappend res [degree $node $g] } lsort -integer -decreasing $res }
As this is ordered, it can equivalently (but often more compactly) 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.
proc degreeHistogram g { set dS [degreeSequence $g] for {set i 0} {$i<=[lindex $dS 0]} {incr i} {set a($i) 0} foreach i $dS {incr a($i)} set res {} foreach i [lsort -integer [array names a]] { lappend res $a($i) } set res }
Some examples:
(above) 0 4 2 2 2 K5 : 0 0 0 0 0 5 (a pentagram inside a pentagon) K3,3 : 0 0 0 6 (the famous Gas-Water-Electricity graph)
A 5-legged star is 0 5 0 0 0 1, with stars having the nice property that g card(E)=1 and g1 = card(E):
proc isStar g { set dH [degreeHistogram $g] set n [lindex $dH 1] expr [lindex $dH $n]==1 && [join $dH +]==$n+1 }
A complete graph, where every vertex is connected with each, like K5 above, satisfies gi = card(E) when i=card(E); otherwise 0:
proc isComplete g { set dH [degreeHistogram $g] expr [lindex $dH end]==[join $dH +] }
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.
Lovely question, Richard. While it's been decades since I've done any graph theory, and I don't yet know of useful on-line resources for more than glossary information, I can tell you that the general case is even worse than this: it's not just that the degree histogram doesn't determine a graph, but that there is no known polynomial-time calculation which can compute whether two graphs are isomorphic. There's plenty of research still to do in this area.