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, \ldots, 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)\).