Some characterizations of gamma and beta-acyclicity of hypergraphs
David Duris · HAL (Le Centre pour la Communication Scientifique Directe) · 2008
The notions of $\gamma$ and $\beta$-acyclicity are two classic generalizations of the acyclicity of graphs to hypergraphs. They satisfy the property that, if a hypergraph is $\gamma$-acyclic then it is $\beta$-acyclic, and the reverse is false. We give some new properties concerning these notions. First we show that we can strictly insert another notion of acyclicity between them, namely the fact of having a join tree with disjoint branches. And if we add a condition on the existence of such a join tree, we obtain a notion equivalent to $\gamma$-acyclicity. Then we present two characterizations, consisting in applying successively a small set of rules, deciding $\gamma$ and $\beta$-acyclicity respectively.