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?
Asked
Viewed
129 times
7
$\begingroup$
$\endgroup$
-
$\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
