Answers are grounded in this paper and cite their sources.
Study introduces r-uniform hypergraphs, evaluating their properties and computational methods for hypergraph parameters.
In this work, we introduce and study a generalization for r-uniform hypergraphs of complement-reducible graphs, the so-called co-graphs. The operations for r-join-hypergraphs are the binary disjoint union of two given r-join-hypergraphs and the r-nary join, which inserts all possible hyperedges of cardinality r, each including exactly one vertex from each of r given r-join-hypergraphs. We characterize the primal graphs of r-join-hypergraphs as special co-graphs and give some properties of r-join-hypergraphs. This allows us to give a method that decides whether an r-uniform input hypergraph H is an r-join-hypergraph and, in the case of an affirmative answer, finds a decomposition tree for H in polynomial time. This task proved to be challenging. We show specific formulas for computing various hypergraph parameters for r-uniform hypergraphs defined by the binary disjoint union of two r-uniform hypergraphs and the r-nary join of rr-uniform hypergraphs. The parameters considered 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 largest matching, the size of a smallest dominating set, the chromatic number, the strong chromatic number, and the upper chromatic number. This yields O(n·r)-time algorithms to compute these values on r-join-hypergraphs on n vertices given by a decomposition tree. Of particular interest is the development of an efficient algorithm to compute the size of a largest matching. In addition, we infer relations among the considered parameters restricted to r-join-hypergraphs. Our methods generalize and reprove a number of results that are known for co-graphs.
No takes yet. Share an insight, caveat, or question.
Gurski et al. (2026) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: