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
    
googling gave me "Havel-Hakimi theorem".. Which i am not sure gives the required output. –  Maverickgugu Jun 25 '11 at 6:21
add comment

1 Answer

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

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.