Computing at Glasgow University
Paper ID: 9352
DCS Tech Report Number: TR-2010-318

Diamond-free Degree Sequences
Miller,A. Prosser,P.

Publication Type: Tech Report (internal)
Appeared in: DCS Technical Report Series
Page Numbers : 1 to 9
Publisher: Dept of Computing Science, University of Glasgow
Year: 2010

We introduce a new problem, to generate all degree sequences that have a corresponding diamond-free graph with secondary properties. This problem arises naturally from a problem in mathematics to do with balanced incomplete block designs; we devote a section of this paper to this. The problem itself is challenging with respect to computational effort arising from the large number of symmetries within the models. We introduce two models for this problem. The second model is an improvement on the first, and this improvement largely consists of breaking the problem into two stages, the first stage producing graphical degree sequences that satisfy arithmetic constraints and the second part testing that there exists a graph with that degree sequence that is diamond-free. We present the problem in detail and then give motivation for it. Two models are then presented, along with a listing of solutions.

Keywords: constraint programming diamond-free graphs balanced incomplete block designs

PDF Bibtex entry Endnote XML