Synthesis of Biconnected Graphs

F. T. Boesch, J. A.M. Mchugh

Research output: Contribution to journalArticlepeer-review

5 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)330-334
Number of pages5
JournalIEEE Transactions on Circuits and Systems
VolumeCAS-21
Issue number3
DOIs
StatePublished - May 1974
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Engineering(all)

Fingerprint Dive into the research topics of 'Synthesis of Biconnected Graphs'. Together they form a unique fingerprint.

Cite this