Realizability, primality and criticality of Hypergraphs
Mohamed Zaidi, Abderrahim Boussaïri, Brahim Chergui, Pierre Ille
Academic Editor: Youssef EL FOUTAYENI
Received |
Accepted |
Published |
06 February 2020 |
21 February 2020 |
10 March 2020 |
Abstract: Given a 3-uniform hypergraph H, a subset M of V (H) is a module of H if for each e ∈ E(H) such that e ∩ M ≠ ∅ and e \ M ≠ ∅, there exists m ∈ M such that e ∩ M = {m} and for every n ∈ M, we have (e\{m})∪{n} ∈ E(H). For example, ∅, V (H) and {v}, where v ∈ V (H), are modules of H, called trivial. A 3-uniform hypergraph is prime if all its modules are trivial. Let H be a 3-uniform hypergraph. A tournament T defined on V(T)= V (H) is a realization of H if the edges of H are exactly the 3- element subsets of V(T) that induce 3-cycles. Given a prime 3-uniform hypergraph, we study its prime, 3- uniform and induced sub-hypergraphs. Our main result is: given a prime 3-uniform hypergraph H, with v(H) ≥ 4, there exist v, w ∈ V (H) such that H − {v, w} is prime.