EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Complement Reducible Uniform Hypergraphs

Frank Gurski, Jochen Rethmann

Axioms · 10.04.2026 · 15 (4) · 278

DOI: 10.3390/axioms15040278 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Axioms, online erschienen am 10.04.2026. Verfasst von Frank Gurski und 1 weiteren Autor:innen. Die Arbeit wurde bisher 1-mal zitiert (Crossref) und nennt 52 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We investigate a generalization of complement reducible graphs, called co-graphs, for r-uniform hypergraphs. The operations of r-co-hypergraphs are the disjoint union of two given r-co-hypergraphs and the join operation, which inserts all hyperedges of cardinality r between the non-empty vertex subsets of two given r-co-hypergraphs. We show that the primal graphs of r-co-hypergraphs are special co-graphs and that r-co-hypergraphs are closed under complementation of r-uniform hypergraphs. This leads to a method that can determine whether an input hypergraph H is an r-co-hypergraph. If the answer is positive, we find a decomposition tree for H in polynomial time. We give specific formulas for how to compute several hypergraph parameters for r-uniform hypergraphs defined by the disjoint union of two r-uniform hypergraphs and the join of two r-uniform hypergraphs. The considered parameters are the size of a largest stable set, the size of a largest co-stable set, the size of a largest independent set, the size of a largest co-independent set, the size of a smallest vertex cover, the size of a smallest 2-transversal, the size of a smallest dominating set, the strong chromatic number, and the upper chromatic number. This leads to O(n) time algorithms to compute these values on r-co-hypergraphs on n vertices given by a decomposition tree. Further, we conclude relations for the considered parameters restricted to r-co-hypergraphs. Our methods generalize and re-prove several results known for co-graphs.

Zitieren

APA

Gurski, F., & Rethmann, J. (2026). Complement Reducible Uniform Hypergraphs. Axioms, 15(4), 278. https://doi.org/10.3390/axioms15040278

Vancouver

Gurski F, Rethmann J. Complement Reducible Uniform Hypergraphs. Axioms. 2026;15(4):278. doi:10.3390/axioms15040278

BibTeX
@article{Gurski2026,
  author = {Gurski, Frank and Rethmann, Jochen},
  title = {Complement Reducible Uniform Hypergraphs},
  journal = {Axioms},
  year = {2026},
  volume = {15},
  number = {4},
  pages = {278},
  doi = {10.3390/axioms15040278}
}
Kostenlos starten →