Incidence graphs of biacyclic hypergraphs

DOI10.1016/0166-218X(95)00070-8MaRDI QIDQ1923616zbMATH OpenOpenAlexFDO

Authors Feodor F. Dragan, V. I. Voloshin

Publication date 28 May 1997

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL http://www.elsevier.com/locate/dam

zbMATH Keywords

chordal bipartite graphshypergraphsincidence graphsneighbourhood orderings

Mathematics Subject Classification ID

Hypergraphs (05C65) Structural characterization of families of graphs (05C75)

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.

Recommendations

• Incidence graphs of bipartite \(G\)-graphs
• scientific article; zbMATH DE number 2152547
• Incidence self complementary hypergraphs
• A note on incidence graphs
• Biclique-Helly graphs
• scientific article; zbMATH DE number 5054167
• Incidence graphs and unneighborly polytopes
• Incidences and the spectra of graphs
• Incidences and the Spectra of Graphs
• scientific article; zbMATH DE number 3887740

Cites work

• Absolute reflexive retracts and absolute bipartite retracts
• Absolute retracts of bipartite graphs
• Characterizations of totally balanced matrices
• Classes of bipartite graphs related to chordal graphs
• Doubly chordal graphs, steiner trees, and connected domination
• Doubly Lexical Orderings of Matrices
• Graphs whose neighborhoods have no special cycles
• scientific article; zbMATH DE number 4093511 (Why is no real title available?)
• scientific article; zbMATH DE number 3758364 (Why is no real title available?)
• scientific article; zbMATH DE number 175723 (Why is no real title available?)
• scientific article; zbMATH DE number 468643 (Why is no real title available?)
• On hypergraph acyclicity and graph chordality

Cited in

(3)

• Subgraph trees in graph theory
• Additive sparse spanners for graphs with bounded length of largest induced cycle
• scientific article; zbMATH DE number 2230303 (Why is no real title available?)

This page was built for publication: Incidence graphs of biacyclic hypergraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1923616)