Matching and domination numbers in r-uniform hypergraphs

Matching and domination numbers in r-uniform hypergraphs

0.00 Avg rating0 Votes
Article ID: iaor20172791
Volume: 34
Issue: 2
Start Page Number: 656
End Page Number: 659
Publication Date: Aug 2017
Journal: Journal of Combinatorial Optimization
Authors: , , ,
Keywords: combinatorial optimization, graphs, heuristics
Abstract:

A matching is a set of pairwise disjoint hyperedges of a hypergraph H. The matching number ν ( H ) equ1 of H is the maximum cardinality of a matching. A subset D of vertices of H is called a dominating set of H if for every vertex v not in D there exists u D equ2 such that u and v are contained in a hyperedge of H. The minimum cardinality of a dominating set of H is called the domination number of H and is denoted by γ ( H ) equ3 . In this paper we show that every r‐uniform hypergraph H satisfies the inequality γ ( H ) ( r 1 ) ν ( H ) equ4 and the bound is sharp.

Reviews

Required fields are marked *. Your email address will not be published.