4
$\begingroup$

Give a sequence of column/row sums, is it possible to determine (other than by brute force) whether there exists a binary, symmetric matrix with the same column/row sums?

I did find this article, http://www.ams.org/journals/mcom/1987-48-178/S0025-5718-1987-0878703-6/home.html, but my math skills aren't good enough to extract what I'm looking for or really determine 100% that this is what I'm talking about

  • 0
    See also http://arxiv.org/abs/1107.1299 authored by Ju & Seo.2012-04-26

1 Answers 1

1

From https://en.wikipedia.org/wiki/Degree_%28graph_theory%29

Hakimi (1962) proved that $(d_1, d_2, ..., d_n)$ is a degree sequence of a simple graph if and only if $(d_2 − 1, d_3 − 1, ..., d_{d_1+1} − 1, d_{d_1+2}, > d_{d_1+3}, ..., d_n)$ is. This fact leads to a simple algorithm for finding a simple graph that has a given realizable degree sequence:

1) Begin with a graph with no edges. 2) Maintain a list of vertices whose degree requirement has not yet been met in non-increasing order of residual degree requirement. 3) Connect the first vertex to the next d1 vertices in this list, and then remove it from the list. Re-sort the list and repeat until all degree requirements are met.

  • 1
    What is dd1+1-1? Is that $d_{d_1+1}-1$?2012-04-26