Degree Realization by Bipartite Cactus Graphs

Abstract

The Degree Realization problem with respect to a graph family $\mathcal{F}$ is defined as follows. The input is a sequence $d$ of $n$ positive integers, and the goal is to decide whether there exists a graph $G \in \mathcal{F}$ whose degrees correspond to $d$. The main challenges are to provide a precise characterization of all the sequences that admit a realization in $\mathcal{F}$ and to design efficient algorithms that construct one of the possible realizations, if one exists.

This paper studies the problem of realizing degree sequences by bipartite cactus graphs (where the input is given as a single sequence, without the bi-partition). A characterization of the sequences that have a cactus realization is already known [Rao 1981]. In this paper, we provide a systematic way to obtain such a characterization, accompanied by a realization algorithm. This allows us to derive a characterization for bipartite cactus graphs, and as a byproduct, for several other interesting sub-families of cactus graphs, including bridge-less cactus graphs and core cactus graphs, as well as for the bipartite sub-families of these families. Finally, we also provide a characterization of forcibly bipartite cactus sequences.