scientific article; zbMATH DE number 4027515

From MaRDI portal
Publication:3768935





There are known many necessary and sufficient conditions for a graph to be an interval graph (e.g. C. C. Lekkerkerker's and J. Ch. Boland's, P. C. Gilmore's and J. J. Hoffman's, B. G. Mirkinn's and S. N. Rodin's). The author gives some new structural properties of interval graphs. The results are described using the denotation I(x) for a set of all vertices which are adjacent to a vertex x (in a graph G) and many other special denotations. Theorem 1. Let \(G=(X,E)\) be the complementary graph of an interval graph. If a,b\(\in X\), \(a\not\in I(b)\) then I(x)\(\supset I(b)\setminus I(a)\), for all \(x\in I(a)\setminus I(b).\) Theorem 2. If \(G=(X,E)\) is a simple nonoriented graph and I(a)\(\supset I(b)\) or I(b)\(\supset I(a)\) for all a,b\(\in X\), \(a\not\in I(b)\) then G is the complementary graph of an interval graph. We omit the theorems 3, 4 using special denotations.











This page was built for publication:

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