The cyclicity of a hypergraph (Q1379823)

This article presents a new generalization of the cyclomatic number of a graph. This is the cyclicity of a hypergraph \(E\), defined as \[ \gamma(E) =\sum_{f: \delta_E(f)>1} \bigl(\delta_E (f)-1\bigr)- \bigl| \text{Max} (E)\bigr |+1, \] where \(\delta_E\) is a notion of `degree' of a subedge \(f\in E\) and \(\text{Max} (E)\) is the set of maximal edges in \(E\). The cyclicity is always nonnegative, equaling 0 only on acyclic hypergraphs, and is monotone increasing on hypergraphs. This paper introduces the notion of the circulant graph \(G\) of a hypergraph \(E\) (essentially, the edges of \(E\) are the vertices of \(G\), and the edges of \(G\) depend on the intersections of the edges of \(E)\), and shows that the cyclicity of \(E\) equals the cyclomatic number of \(G\). The paper concludes with a comparison of cyclicity with the hypergraph cyclomatic number, and also with a few mild generalizations of cyclicity.