Matching And Domination Number Of Hypergraphs And Related Extremal Hypergraphs

Within the past fifty years,the research of graph theory has been blos-somed with the rapid development of science and technology.As an im-portant research direction of graph theory,the study of dominating sets,matchings and transversals in graphs have been wildly applied in related fields,such as computer science,biological system,network communication,artificial intelligence and management science.Hypergraphs,which seem to be the most general and most complex discrete structures,are a natural generalization of undirected graphs.The theory of dominating sets,match-ing and transversals in graphs is well developed,and similar questions in hypergraphs are recently proposed and studied.In this paper,we focus on the domination numbers in hypergraphs and present constructive character-izations of the extremal hypergraphs.First,we propose an upper bound on dominating number of hypergraph H,which is based on its matching number.It is well known that domination number γ(H),matching number v(H)and transversal number T(H)are the most important parameters of hypergraphs.The relationship between T(H)and v(H)in hypergraph H is a long-standing open problem known as Ryser’ s conjecture,which states that if H is r-partitie hypergraph then T(H)≤(r-1)v(H).This conjecture turns to be notoriously difficult,and remains open for r ≥ 4.Motivated by Ryser’s conjecture,we consider about the relationship between the domination number and the matching number,prove that any r-uniform hypergraph H satisfying the inequality y(H)≤(r-1)v(H),and show the bound is sharp by finite projective planar.Secondly,we consider about the construction of hypergraphs satisfy-ing γ(H)=(r-1)v(H).Since hypergraphs are complex,a constructive characterization of extremal hypergraphs with γ(H)＝(r -1)v(H)seems to be difficult in general.We focus on the linear intersecting hypergraphs.By applying the properties of linear intersecting hypergraphs,we show that all the 5-uniform linear intersecting hypergraphs with γ(H)= 4 can be construct by the finite projective planar of order 3.Finally,we discuss the extremal hypergraph with v(H)>2.Recalled all the studies on hypergraphs satisfying γ(H)=(r-1)v(H),we find that the characterizations are merely of intersecting hypergraphs,and the proof is already complicated.According to the properties of linear hypergraphs with v(H)≥ 2,we show the constructive characterization of 4-uniform linear hypergraphs with γ(H)= 6.