TY - JOUR

T1 - Forcibly-biconnected graphical degree sequences

T2 - Decision algorithms and enumerative results

AU - Wang, Kai

N1 - Publisher Copyright:
© 2019 Georgia Southern University. All rights reserved.

PY - 2019

Y1 - 2019

N2 - 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.

AB - 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.

KW - Co-NP

KW - Forcibly biconnected

KW - Graphical degree sequence

KW - Graphical partition

UR - http://www.scopus.com/inward/record.url?scp=85082007757&partnerID=8YFLogxK

U2 - 10.20429/tag.2019.060204

DO - 10.20429/tag.2019.060204

M3 - Article

AN - SCOPUS:85082007757

SN - 2470-9859

VL - 6

JO - Theory and Applications of Graphs

JF - Theory and Applications of Graphs

IS - 2

M1 - 060204

ER -