Dokument: Complement Reducible Uniform Hypergraphs

Titel:	Complement Reducible Uniform Hypergraphs
URL für Lesezeichen:	https://docserv.uni-duesseldorf.de/servlets/DocumentServlet?id=73381
URN (NBN):	urn:nbn:de:hbz:061-20260526-133802-1
Kollektion:	Publikationen
Sprache:	Englisch
Dokumententyp:	Wissenschaftliche Texte » Artikel, Aufsatz
Medientyp:	Text
Autoren:	Gurski, Frank [Autor] Rethmann, Jochen [Autor]
Dateien:	[Dateien anzeigen] Adobe PDF [Details] 411,9 KB in einer Datei [ZIP-Datei erzeugen] Dateien vom 26.05.2026 / geändert 26.05.2026
Stichwörter:	r-co-hypergraphs , hypergraphs , uniform hypergraphs , algorithms , special graph classes , co-graphs
Beschreibung:	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 𝒪(𝑛) 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.
Rechtliche Vermerke:	Originalveröffentlichung: Gurski, F., & Rethmann, J. (2026). Complement Reducible Uniform Hypergraphs. Axioms, 15(4), Article 278. https://doi.org/10.3390/axioms15040278
Lizenz:	Dieses Werk ist lizenziert unter einer Creative Commons Namensnennung 4.0 International Lizenz
Fachbereich / Einrichtung:	Mathematisch- Naturwissenschaftliche Fakultät
Dokument erstellt am:	26.05.2026
Dateien geändert am:	26.05.2026