Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
1  
I take it that by "binary" you mean the entries are all zeros and ones. If you drop the word, "symmetric", there is a thorough discussion in Chapter 6 of Ryser, Combinatorial Mathematics, which is Number 14 in the Carus Mathematical Monographs series published by the Mathematical Association of America. The books in that series are expository in nature. Maybe you can adapt the methods in that chapter to the special case of symmetric matrices. –  Gerry Myerson Apr 25 '12 at 22:47
    
Thanks for the references, I did mean 1/0s. I guess an equivalent problem would be finding whether a undirected graph exists given vertex degrees –  spinning_plate Apr 26 '12 at 0:23
    
It's equivalent if you allow your graphs to have loops, that is, edges joining a vertex to itself. –  Gerry Myerson Apr 26 '12 at 1:16
    
I think it has certain relations with LONESUM matrices. –  hkju Apr 26 '12 at 6:07
    
LONESUM MATRICES are the matrices avoiding the $2 \times 2$ submatrix of the types [[1,0],[0,1]] or [[0,1],[1,0]]. –  hkju Apr 26 '12 at 6:14
show 1 more comment

1 Answer

up vote 1 down vote accepted

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.

share|improve this answer
1  
What is dd1+1-1? Is that $d_{d_1+1}-1$? –  Gerry Myerson Apr 26 '12 at 1:14
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.