Incidence graphs of biacyclic hypergraphs
type: Item
instance of: scholarly article
title: Incidence graphs of biacyclic hypergraphs
zbMATH Open document ID: 0863.05060
DOI: 10.1016/0166-218X(95)00070-8
author: Feodor F. Dragan
author: V. I. Voloshin
published in: Discrete Applied Mathematics
publication date: 1997-05-28T00:00:00Z
full work available at URL: dam
review text: It is known that the incidence graphs of totally balanced hypergraphs are the chordal bipartite graphs. A hypergraph is called acyclic if it is conformal and its 2-section graph is chordal. A hypergraph is called biacyclic if it and its dual are acyclic. In this paper the incidence graphs of biacyclic hypergraphs are characterized as the neighbourhood-Helly graphs whose square is chordal. Equivalently, these graphs are characterized in terms of maximum neighbourhood orderings and in terms of certain retracts with certain forbidden isometric wheels. For a more general investigation of graphs with maximum neighbourhood orderings, see \textit{A. Brandstädt}, \textit{F. F. Dragan}, \textit{V. D. Chepoi} and \textit{V. I. Voloshin} [Dually chordal graphs, Lect. Notes Comput. Sci. 790, 237-251 (1994)]. A corollary is that an irreflexive graph \(G\) is chordal bipartite if and only if every induced subgraph of \(G\) has a maximum neighborhood ordering.
reviewed by: Andreas Brandstädt
Mathematics Subject Classification ID: 05C65
Mathematics Subject Classification ID: 05C75
zbMATH DE Number: 933126
zbMATH Keywords: incidence graphs
zbMATH Keywords: hypergraphs
zbMATH Keywords: chordal bipartite graphs
zbMATH Keywords: neighbourhood orderings
MaRDI profile type: Publication
cites work: Characterizations of totally balanced matrices
cites work: Absolute retracts of bipartite graphs
cites work: Absolute reflexive retracts and absolute bipartite retracts
cites work: Q3941433
cites work: Classes of bipartite graphs related to chordal graphs
cites work: Q3820642
cites work: Graphs whose neighborhoods have no special cycles
cites work: On hypergraph acyclicity and graph chordality
cites work: Q4034774
cites work: Q4272121
cites work: Doubly Lexical Orderings of Matrices
cites work: Doubly chordal graphs, steiner trees, and connected domination
OpenAlex ID: W1979249204
Recommended article: Incidence Graphs of Bipartite G-Graphs
Recommended article: Q4664110
Recommended article: Incidence self complementary hypergraphs
Recommended article: A note on incidence graphs
Recommended article: Biclique-Helly graphs
Recommended article: Q5488350
Recommended article: Q3116025
Recommended article: Incidences and the spectra of graphs
Recommended article: Incidences and the Spectra of Graphs
Recommended article: Q3222234
description: scientific article; zbMATH DE number 933126