Diamond Free

We now have code to generate the unique set of degree sequences for a graph with n
vertices such that the degree sequence satisfies the following constraints

 - each vertex has non-zero degree
 - each vertex degree is mod 3
 - the sum of the degrees is mod 12
 - there exists a simple diamond-free graph with tha degree sequence

By a "simple diamond-free graph" we mean that

 - the the graph has an 0/1 adjacency matrix A
 - A[i][i] = 0 (no loops)
 - A[i][j] = A[j][i] (symmetrc)
 - for all i<j<k<l A[i][j] + A[i][k] + A[i][l] + A[j][k] + A[j][l] + A[k][l] < 5

Code to Generate Diamond Free graphs
We have two ways of doing this. The first is a single shot, the other two phase

Single Shot (DiamondFree3)
 We generate degree sequences that are grapical, in increasing order of degree sequence
 and for each sequence we test if it has a corresponding diamond free graph.

Two Phase (GetDegSeq and GetDiamondFree)
 We generate a file of all degree sequences that are graphical and satisfy the
 constraints on modularity and summation. The second phase reads in this file and
 for each degree sequence attempts to create a diamond-free graph with this degree sequence.

Verification (Verify)
The output can be verified seperately. That is, both of the above programs output
satisfying degree sequences with a corresponding adjacency matrix. The Verify program checks 
that the following

  - the degree sequence is compliant
    - each degree is mod 3
    - sum of degrees is mod 12
  - the adjacency matrix corresponds to a simple graph
    - A[i][i] = 0
    - A[i][j] = A[j][i]
  - the adjacency matrix corresponds to the degree sequence
  - the corresponding graph is diamond-free

The code is relatively fast and is in the following directory

  pat/public_html/jchoco/diamondFree

NOTE: we can plot/draw these graphs if we want.


Patrick Prosser 
03/08/2010