The cyclicity of a hypergraph Original Research Article

The cyclicity of a hypergraph is an efficiently computable integer that extends the notion of the cyclomatic number of a graph. Generalizing the notion of the degree of a node in a graph, we define the star articulation degree of a subedge in a hypergraph, and then use it to set up the expression for the cyclicity. The basic properties of cyclicity are that it is zero on acyclic hypergraphs and strictly positive otherwise, and that on graphs it coincides with the cyclomatic number; moreover, the cyclicity depends only on maximal edges, decreases on subhypergraph, and is additive on compositions. We introduce the notions of circulant graphs and join-graphs of a hypergraph. Neither of these two kinds of graphs is uniquely determined by a hypergraph; however, every circulant graph and every join-graph of a hypergraph has the cyclomatic number equal to the cyclicity of the hypergraph. We also compare the cyclicity of a hypergraph with the cyclomatic number of a hypergraph, which is another, already known, extension of the cyclomatic number of a graph.