Two-step graphs of trees

DOI10.1016/0012-365X(93)90122-AMaRDI QIDQ688263zbMATH OpenWikidataFDO

Authors J. Richard Lundgren, Craig Rasmussen

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)90122-A

zbMATH Keywords

competition graphsinterval graphtreestwo-step graph

Mathematics Subject Classification ID

Trees (05C05) Structural characterization of families of graphs (05C75) Graph theory (05C99)

Review text

Two-steps graphs (see the review Zbl 0790.05036 below) of trees are examined in two contexts. First, they are considered as competition graphs, and necessary and sufficient conditions are given for the competition graph of a tree to be an interval graph. Then, the problem of constructing the tree \(T\) from its two-step graph \(S_ 2(T)\) is considered. A class of trees where this is possible is found.

Recommendations

• On the trees whose 2-step competition numbers are two.
• scientific article; zbMATH DE number 1558366
• A characterization of graphs with interval two-step graphs
• scientific article; zbMATH DE number 1161337
• The \(m\)-step competition graph of a digraph

Cites work

• A characterization of competition graphs
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 4139769 (Why is no real title available?)
• scientific article; zbMATH DE number 3912431 (Why is no real title available?)
• scientific article; zbMATH DE number 4025487 (Why is no real title available?)
• scientific article; zbMATH DE number 4070952 (Why is no real title available?)
• scientific article; zbMATH DE number 3679862 (Why is no real title available?)
• scientific article; zbMATH DE number 15260 (Why is no real title available?)
• scientific article; zbMATH DE number 975363 (Why is no real title available?)
• Interval competition graphs of symmetric digraphs
• Inverting graphs of rectangular matrices
• Representation of a finite graph by a set of intervals on the real line

Cited in

(12)

• The \(m\)-step competition graph of a digraph
• Connected triangle-free \(m\)-step competition graphs
• A characterization of graphs with interval two-step graphs
• Chromatic numbers of competition graphs
• Graph equation for line graphs and \(m\)-step graphs
• Structural properties and hamiltonicity of neighborhood graphs
• Graphs with at most two trees in a forest-building process
• A class of acyclic digraphs with interval competition graphs
• Injective coloring of graphs revisited
• On the trees whose 2-step competition numbers are two.
• scientific article; zbMATH DE number 4025487 (Why is no real title available?)
• scientific article; zbMATH DE number 125494 (Why is no real title available?)

This page was built for publication: Two-step graphs of trees

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