No label defined (Q3768935)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 4027515
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 4027515 |
Statements
1986
0 references
interval graph
0 references
structural properties
0 references
complementary graph
0 references
0.7800765633583069
0 references
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.
0 references