Degree histograms

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 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)-1; 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 (but see below for {0 0 4} ambiguities!)

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.

RS Further experiments show that in general graphs, non-isomorphic sets are easily found: 0 0 4 may stand for a "square", two disconnected pairs of parallel edges, or four disconnected loops. So let's limit the scope to simple graphs, which are mostly used anyway. Whether disconnected graphs may cause ambiguities, remains as question to the reader ;-)

CL Even smaller: Two not simple, non isomorphic 0 0 2 graphs one connected, the other not connected.

       /\             ___   ___
      x  x            \ /   \ /
       \/              x     x

Next is to think about simple graphs. RS: OK, enumerating all degree histograms for simple graphs with 4 or less vertices:

 0    {empty graph}
 1    .
 2    ..
 02   -
 3    ...
 12   .-
 021  >
 003  triangle
 4    ....
 22   .. -
 04   - -
 022  |_|
 103  triangle .
 121  |_ .
 0121 triangle with a loose leg
 004  square
 0022 square with one diagonal
 0004 square with two diagonals
 0301 three-legged star

Looks good so far... Notice that unconnected graphs can be composed simply by elementwise addition, so e.g 103 = 003 & 1. For connected graphs, rules seem to be more complicated.- Further experiments with 5 vertices show a case of non-isomorphics distinguished by connectedness:

 023 triangle - /or/ M

So we'll have to exclude disconnected graphs if we want to strive for isomorphy.- But also that gets falsified by the simple 0 0 4 2 which describes two hexagons with a chord (an additional connection between two vertices), one forming a triangle at a side, one going through the middle and forming two trapezes. Well..

[RS and CL briefly converse. RS observes:] "My last idea was that in addition to degree histogram, I'd also need a histogram over induced cycles, because that's the minimal distinction in the 0 0 4 2 non-isomorphy. This would involve: first enumerate all induced cycles, then cast them into a histogram according to their length - in that case 0 0 0 1 0 1 vs. 0 0 0 0 2."

[CL relays a challenge from a correspondent:] "As the mean of the degree histogram increases how does the number of non-isomorphic degree-matched graphs increase?" See also:

Category Graph theory