Extremal hypergraphs for matching number and domination number

摘要

A matching in a hypergraph H is a set of pairwise disjoint hyperedges. The matching number v(H) of H is the size of a maximum matching in H. A subset D of vertices of H is a dominating set of H if for every v is an element of V D there exists u is an element of D such that u and v lie in an hyperedge of H. The cardinality of a minimum dominating set of H is the domination number of H, denoted by gamma(H). It was proved that gamma(H) = (r - 1)v(H) for r -uniform hypergraphs and the 2 -uniform hypergraphs (graphs) achieving equality gamma(H) = v(H) have been characterized. In this paper we generalize the inequality gamma(H) = (r - 1)v(H)to arbitrary hypergraph of rank r and we completely characterize the extremal hypergraphs H of rank 3 achieving equality gamma(H) = (r - 1)v(H). (C) 2017 Elsevier B.V. All rights reserved.