Enumeration of the Degree Sequences of $3$-Connected Graphs and Cactus Graphs

Abstract

The necessary and sufficient conditions for a given sequence of positive integers $d_1,d_2,\dots ,d_n$ to be the degree sequence of $3$-connected graphs and cactus graphs are proved respectively by S. L. Hakimi [5] and A. R. Rao [6]. In this note, we utilize these results to prove a formula for the functions $d_{tc}(2m)$ and $d_{ca}(2m)$, the number of degree sequences with degree sum $2m$ by $3$-connected graphs and cactus graphs respectively. We give generating function proofs and elementary proofs of the formulas $d_{tc}(2m)$ and $d_{ca}(2m)$.