Radius versus diameter in cocomparability and intersection graphs (Q1356529)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Radius versus diameter in cocomparability and intersection graphs |
scientific article |
Statements
Radius versus diameter in cocomparability and intersection graphs (English)
0 references
9 September 1997
0 references
Let \(r\) be the radius and \(d\) the diameter of a given graph. Then evidently \(r\leq d \leq 2r\) and this has been shown to be sharp in general. For a cocomparability graph of a partially ordered set (with edges between all incomparable pairs) one has \(2r \leq d+3\). The intersection graph of a finite family of sets has edges between all nondisjoint pairs. For a trapezoid graph, i.e. the intersection graph of a family a trapezes between two fixed parallel lines, \(2r \leq d+2\) holds. For a (proper) circular-arc graph, i.e. the intersection graph of a (pairwise incomparable) set of arcs of a fixed circle, we have \(d\leq r+2\) (\(d\leq r+1\)).
0 references
radius
0 references
diameter
0 references
cocomparability graph
0 references
trapezoid graph
0 references
circular-arc graph oscillators
0 references