Synthesis of Biconnected Graphs

In this investigation, it is necessary to distinguish pseudo- graphs (self-loops and multiple lines allowed), multigraph (no self-loops but multiple lines are allowed), and graphs (neither self-loop nor multiple lines allowed). The problem of synthesizing graphs, multigraphs, and pseudographs having a prescribed degree sequence was solved by Hakimi. He also determined the conditions under which a connected realization exists in each of these three cases. The case of biconnected (nonseparable) realizations of a degree sequence was given by Hakimi forthe case of pseudographs and multigraphs. His methods did not apply to the case of graphs. The triconnected case was solved by Rao and Rao for graphs; however, strangely enough, the biconnected case apparently remains unpublished. We shall show here that the biconnected case can be handled by a “surgery” technique similar in spirit to the connected case given by Hakimi. Several remarks concerning the general n-connected case for pseudographs, multigraphs, and graphs will be given. We conclude with a status report on this subject, which includes the most recent work of Hakimi, Wang and Kleitman, and Bondy.