Forcibly-biconnected graphical degree sequences: Decision algorithms and enumerative results

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

We present an algorithm to test whether a given graphical degree sequence is forcibly biconnected. The worst case time complexity of the algorithm is shown to be exponential but it is still much better than the previous basic algorithm for this problem. We show through experimental evaluations that the algorithm is efficient on average. We also adapt the classic algorithm of Ruskey et al. and that of Barnes and Savage to obtain some enumerative results about forcibly biconnected graphical degree sequences of given length n and forcibly biconnected graphical partitions of given even integer n. Based on these enumerative results we make some conjectures such as: when n is large, (1) the proportion of forcibly biconnected graphical degree sequences of length n among all zero-free graphical degree sequences of length n is asymptotically a constant C (0 < C < 1); (2) the proportion of forcibly biconnected graphical partitions of even n among all forcibly connected graphical partitions of n is asymptotically 0.

Original languageEnglish
Article number060204
JournalTheory and Applications of Graphs
Volume6
Issue number2
DOIs
StatePublished - 2019

Scopus Subject Areas

  • Theoretical Computer Science
  • Numerical Analysis
  • Discrete Mathematics and Combinatorics

Keywords

  • Co-NP
  • Forcibly biconnected
  • Graphical degree sequence
  • Graphical partition

Fingerprint

Dive into the research topics of 'Forcibly-biconnected graphical degree sequences: Decision algorithms and enumerative results'. Together they form a unique fingerprint.

Cite this