Interval competition graphs of symmetric digraphs

DOI10.1016/0012-365X(93)90121-9MaRDI QIDQ688262zbMATH OpenOpenAlexFDO

Authors J. Richard Lundgren, Craig Rasmussen, John S. Maybee

Publication date 9 June 1994

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365x(93)90121-9

zbMATH Keywords

competition graphsinterval graphsymmetric digraphtwo-step graph

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Directed graphs (digraphs), tournaments (05C20) Structural characterization of families of graphs (05C75) Graph theory (05C99)

Review text

The authors study competition graphs introduced by \textit{A. Raychaudhuri} and \textit{F. S. Roberts} [Methods Oper. Res. 49, 295-311 (1985; Zbl 0572.05050)]. They show that, given a loopless symmetric digraph \(H\), its competition graph is the two-step graph \(S_ 2(H)\) where two vertices of \(H\) are adjacent provided there is a path of length two between them. Moreover they give necessary and sufficient conditions on \(H\) under which \(S_ 2(H)\) is an interval graph or a unit interval graph. Thus they answer a question posed by Raychaudhuri and Roberts (1985).

Recommendations

• scientific article; zbMATH DE number 1145906
• scientific article; zbMATH DE number 140094
• scientific article; zbMATH DE number 1247730
• scientific article; zbMATH DE number 3889550
• \((i,j)\) competition graphs

Cites work

• A Characterization of Comparability Graphs and of Interval Graphs
• scientific article; zbMATH DE number 3889550 (Why is no real title available?)
• scientific article; zbMATH DE number 3853101 (Why is no real title available?)
• scientific article; zbMATH DE number 4149959 (Why is no real title available?)
• scientific article; zbMATH DE number 3912431 (Why is no real title available?)
• scientific article; zbMATH DE number 15260 (Why is no real title available?)
• scientific article; zbMATH DE number 3307330 (Why is no real title available?)
• scientific article; zbMATH DE number 3307331 (Why is no real title available?)
• Representation of a finite graph by a set of intervals on the real line
• Space graphs and sphericity
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms

Cited in

(12)

• A characterization of graphs with interval two-step graphs
• Chromatic numbers of competition graphs
• Structural properties and hamiltonicity of neighborhood graphs
• The m-step competition graphs of doubly partial orders
• The competition hypergraphs of doubly partial orders
• Characterization of digraphs with equal domination graphs and underlying graphs
• A class of acyclic digraphs with interval competition graphs
• scientific article; zbMATH DE number 7217245 (Why is no real title available?)
• scientific article; zbMATH DE number 140094 (Why is no real title available?)
• scientific article; zbMATH DE number 1145906 (Why is no real title available?)
• Two-step graphs of trees
• On CCE graphs of doubly partial orders

This page was built for publication: Interval competition graphs of symmetric digraphs

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