The cyclicity of a hypergraph
type: Item
instance of: scholarly article
title: The cyclicity of a hypergraph
zbMATH Open document ID: 0892.05036
DOI: 10.1016/S0012-365X(97)00133-7
author: France Dacar
published in: Discrete Mathematics
publication date: 1998-07-27T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C65
zbMATH DE Number: 1121485
zbMATH Keywords: cyclomatic number
zbMATH Keywords: cyclicity
zbMATH Keywords: hypergraph
zbMATH Keywords: circulant graph
reviewed by: Gregory Loren McColm
MaRDI profile type: Publication
cites work: Hypergraphs with cyclomatic number zero, triangulated graphs, and an inequality
cites work: On the Desirability of Acyclic Database Schemes
cites work: Q3993087
full work available at URL: s0012-365x(97)00133-7
OpenAlex ID: W4210251051
description: scientific article; zbMATH DE number 1121485