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 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.