Degree Realization by Bipartite Cactus Graphs
Journal of Graph Algorithms and Applications · 19.03.2026 · 30 (1) · 65-87
DOI: 10.7155/jgaa.v30i1.3133 ↗Kurz gefasst
Fachartikel in der Zeitschrift Journal of Graph Algorithms and Applications, online erschienen am 19.03.2026. Verfasst von Amotz Bar-Noy und 4 weiteren Autor:innen. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).
Abstract (Originalsprache)
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.
Zitieren
APA
Bar-Noy, A., Boehnlein, T., Peleg, D., Ran, Y., & Rawitz, D. (2026). Degree Realization by Bipartite Cactus Graphs. Journal of Graph Algorithms and Applications, 30(1), 65-87. https://doi.org/10.7155/jgaa.v30i1.3133
Vancouver
Bar-Noy A, Boehnlein T, Peleg D, Ran Y, Rawitz D. Degree Realization by Bipartite Cactus Graphs. Journal of Graph Algorithms and Applications. 2026;30(1):65-87. doi:10.7155/jgaa.v30i1.3133
BibTeX
@article{BarNoy2026,
author = {Bar-Noy, Amotz and Boehnlein, Toni and Peleg, David and Ran, Yingli and Rawitz, Dror},
title = {Degree Realization by Bipartite Cactus Graphs},
journal = {Journal of Graph Algorithms and Applications},
year = {2026},
volume = {30},
number = {1},
pages = {65--87},
doi = {10.7155/jgaa.v30i1.3133}
}
EUVIMED