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.

Given the degree sequence, is there an algorithm that can return a graph G which satisfies the degree sequence?

There can be more than one graph available for a degree sequence. It is enough if the algorithm returns only one of them.

Assume: Undirected graph, no weights, not a multi-graph(only one edge between 2 vertices).

share|improve this question
    
Invalidity checks: 1. Sum of degrees is even (undirected) 2. Each degree < n Are there any more invalidity checks i can deduce from the degree sequence input? –  Maverickgugu Jun 25 '11 at 6:18
1  
googling gave me "Havel-Hakimi theorem".. Which i am not sure gives the required output. –  Maverickgugu Jun 25 '11 at 6:21
add comment

2 Answers 2

See this Wikipedia section and the first paper available here; you can also search on 'Hakimi-Havel algorithm'.

share|improve this answer
add comment

The degree sequence algorithm that I am speaking of is as follows: (1) Start with the terms of the sequence in decreasing order, (2) Remove the largest term, m, and reduce the next m terms by one, and (3) rearrange the new sequence in decreasing order.

Proving this however is more of a challenge.

share|improve this answer
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.