Forcibly-biconnected Graphical Degree Sequences: Decision Algorithms and Enumerative Results

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.

Abstract licence: CC BY

11 more references, whose wording the paper’s licence keeps private.

A person counts once a day per paper. We keep no cookie and no address: a reader is a hash that changes every day. Any month under five reads shows no number.