The cyclicity of a hypergraph (Q1379823): Difference between revisions
From MaRDI portal
Set profile property. |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: Hypergraphs with cyclomatic number zero, triangulated graphs, and an inequality / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the Desirability of Acyclic Database Schemes / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3993087 / rank | |||
Normal rank |
Revision as of 11:13, 28 May 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The cyclicity of a hypergraph |
scientific article |
Statements
The cyclicity of a hypergraph (English)
0 references
27 July 1998
0 references
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.
0 references
cyclomatic number
0 references
cyclicity
0 references
hypergraph
0 references
circulant graph
0 references