A characterization of graphs with interval two-step graphs

DOI10.1016/0024-3795(94)00173-BMaRDI QIDQ1805321zbMATH OpenFDO

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

Publication date 12 September 1995

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0024-3795(94)00173-B

Gilmore-Hoffman characterization girth interval graph maximal cliques two-step graph

Extremal problems in graph theory (05C35) Paths and cycles (05C38) Structural characterization of families of graphs (05C75)

Review text

The two-step graph \(S_ 2(G)\) of a graph \(G= (V, E)\) is the graph \((V, E')\), where \(\{x, y\}\in E'\) iff \(x\) and \(y\) have a common neighbour. This concept is the undirected analog of competition graphs introduced in [\textit{J. Cohen}, Food webs and niche spaces, Princeton U.P., Princeton, N.J. (1968)]. It is first shown that if the girth of \(G\) is 5 or \(\geq 7\) then \(S_ 2(G)\) cannot be an interval graph. Then the Gilmore-Hoffman characterization of interval graphs is introduced: a graph \(G\) is interval iff the family of maximal cliques has a consecutive ranking---that is, can be ordered \(C_ 1,C_ 2,\dots, C_ r\) so that if \(v\in C_ i\) and \(v\in C_ k\), \(i\leq k\), then \(v\in C_ j\) for all \(j\) with \(i\leq j\leq k\). This characterization is used to find criteria for \(S_ 2(G)\) to be an interval graph for several classes of graphs: trees, graphs with neither triangles nor 6-cycles, graphs with no 6-cycles such that every edge is in a triangle, graphs with no 6- cycles, and graphs with no triangles such that no two 6-cycles share more than one edge.

Recommendations

Cites work

Cited in

(7)

This page was built for publication: A characterization of graphs with interval two-step graphs

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