I am interested in constructing simple connected graphs where each vertex has a fixed number of edges (degree) ahead of time. I had originally assume I could use some modification of the Havel-Hakimi algorithm to do this, but Havel-Hakimi isn't actually guaranteed to produce connected graphs. Are there any known algorithms to do this?

  • $\begingroup$ Thank you for your comment; you are entirely correct! I somehow completely missed that; I have updated my question accordingly. $\endgroup$ – Eric J Aug 8 '18 at 22:51
  • $\begingroup$ Cool. Is this answered by the references/answers at math.stackexchange.com/q/61361/14578 and math.stackexchange.com/q/732303/14578? (Oh, and welcome to CS.SE!) $\endgroup$ – D.W. Aug 8 '18 at 23:49
  • 1
    $\begingroup$ Does each vertex have a maximum degree fixed ahead of time, or is the exact desired degree known for each vertex? $\endgroup$ – Stella Biderman Aug 9 '18 at 2:33
  • $\begingroup$ @StellaBiderman I know the exact desired degree for each vertex. $\endgroup$ – Eric J Aug 9 '18 at 2:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.