Transversal Of Hypergraphs

Hypergraph is generalization of general graph, covering of general graph is an important part of graph theory. Transversal of hypergraph, being generalization of covering for general graph, its meanings are more profound, and its applications are more wide.In this paper, we refer to transversal of hypergraph and its relevant results.In Section One, we introduce general concepts.Transversal hypergraph has wide applications in various fields. It is emphasis on all of work that how to determine transversal hypergraph. In Section Two, an algorithm, called Boole algorithm, to determine transversal hypergraph of any a hypergraph is introduced. In Subsection 2.1 and Subsection 2.2, Boole algorithm are proved. Its steps are as follows:Step 1: For every edge E_j ={v_j1,v_j2,···,v_j|Ej|},define its Boole expression:φ_j=(?)Step 2: For hypergraph H = (E₁, E₂,···,E_m), define its Boole expression:φ(H) =(?)Step 3: Forφ(H), apply Boole operation to it until get the most reduced expression:σ(TrH)=(?)Step 4: Every vertex set T_t corresponding toσ_t inσ(TrH) is a minimal transversal of H. Furthermore, transversal hypergraph TrH = (T₁,T₂,···,T(|Trh|)).On the basis of above steps, we discuss the complexity of Boole algorithm:Theorem 2.2.1 Let the H be hypergraph, if |H|=m, and sup-rank of H be q, then the complexity of Boole algorithm of H is o(q^2m).In Subsection 2.3, two classical results are proved by Boole algorithm and Dual principle in Boole Algebra. They are as follows:Corollary 2.3.1 If H and H' be two simple hyper graphs, then H' = TrH if and only if H = TrH'.Corollary 2.3.2 If H be a simple hypergraph, then Tr(TrH)=H.It follows from above Corollaries that a related question is proposed: which hypergraphs satisfy that their transversal hypergraphs are themselves? Three classes of hypergraphs:Lavas(?)s hypergraph, Fan hypergraph and projective plane PG(3), are found and proved by Boole algorithm (See Proposition 2.3.1, Proposition 2.3.2, Proposition 2.3.3).Study of the transversal number has practical background, esp in optimization theory. In Section Three, the transversal number of three classes of hypergraphs are given.In Subsection 3.1 and Subsection 3.2, the transversal number of complete p-partitioned hypergraph and uniform hypergraph with fixed order and the number of edges, respectively,are given:Theorem 3.1.1Ï„(K_{n1,n2,···,np}^{r₁,r₂,···,r_p})=min(n₁-r_i+1)(i∈{1, 2,···,p})Theorem 3.2.1 Let H be a r-uniform hypergraph on V, if |V|= n, |H|=m, thenÏ„(H)≤n-(n-(?))((?))^?.In Subsection 3.3, a relation of circle-interval hypergraph is mainly given:Theorem 3.3.2 Let H be a circle-interval hypergraph, thenÏ„(H)=[Ï„^*(H)]According to concept of fractional transversal number, the transversal numbers of special circle-interval hypergraphs are given (See Corollary 3.3.1, Corollary 3.3.2, Corollary3.3.4).Section Four is based on a question to relevant (p, t) property of hypergraph proposed by famous scholar-Erd(o|¨)s.In Subsection 4.1 and Subsection 4.2, by means of relevant concepts and definitions, a sufficient condition, of possessing (p, t) property for a hypergraph, is given:Theorem 4.2.2 Let t≥2 and H' be a partial hypergraph consisting of arbitrary p edges of hypergraph H. If there is no such t+l vertices in V(H') and no such t+l edges in H' so that each vertice exactly belongs to one edge , then H possesses (p, t) property.In Subsection 4.3, we study (p,r) property of the projective plane PG(r). Its main result is:Theorem 4.3.1 If PG(r) exists, then PG(r) possesses (2r-2,r-1) property.Furthermore, we also study: for when r=2,3,4, the maximum value p=2,5,9, respectively, of (p, r-1) property for PG(r), are given (See Proposition 4.3.1, Proposition 4.3.2, Proposition 4.3.3).