EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Degree Realization by Bipartite Cactus Graphs

Amotz Bar-Noy, Toni Boehnlein, David Peleg, Yingli Ran, Dror Rawitz

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

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →