Back to Search
Start Over
Extremal hypergraphs for matching number and domination number.
- Source :
-
Discrete Applied Mathematics . Feb2018, Vol. 236, p415-421. 7p. - Publication Year :
- 2018
-
Abstract
- A matching in a hypergraph H is a set of pairwise disjoint hyperedges. The matching number ν ( 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 ∈ V ∖ D there exists u ∈ 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 γ ( H ) . It was proved that γ ( H ) ≤ ( r − 1 ) ν ( H ) for r -uniform hypergraphs and the 2-uniform hypergraphs (graphs) achieving equality γ ( H ) = ν ( H ) have been characterized. In this paper we generalize the inequality γ ( H ) ≤ ( r − 1 ) ν ( H ) to arbitrary hypergraph of rank r and we completely characterize the extremal hypergraphs H of rank 3 achieving equality γ ( H ) = ( r − 1 ) ν ( H ) . [ABSTRACT FROM AUTHOR]
- Subjects :
- *HYPERGRAPHS
*GRAPH theory
*FUZZY hypergraphs
*MATHEMATICS
*GENERALIZATION
Subjects
Details
- Language :
- English
- ISSN :
- 0166218X
- Volume :
- 236
- Database :
- Academic Search Index
- Journal :
- Discrete Applied Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 126943944
- Full Text :
- https://doi.org/10.1016/j.dam.2017.10.019