Distances in cocomparability graphs and their powers (Q1183347): Difference between revisions
From MaRDI portal
Changed an Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(One intermediate revision by one other user not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4099676 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The <i>k</i>-Domination and <i>k</i>-Stability Problems on Sun-Free Chordal Graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3808118 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3971999 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Topics on perfect graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On powers and centers of chordal graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4918387 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3783331 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4032992 / rank | |||
Normal rank |
Latest revision as of 15:45, 15 May 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Distances in cocomparability graphs and their powers |
scientific article |
Statements
Distances in cocomparability graphs and their powers (English)
0 references
28 June 1992
0 references
All graphs considered are finite and connected. For any nonnegative integer \(i\), let \(\Gamma_ i\) denote the class of graphs obeying some linear ordering \(v_ 1< v_ 2<\cdots<v_ n\) of its vertices such that \(d(x,y)+d(y,z)\leq d(x,z)+i\) holds for all vertices \(x<y<z\). It is easy to see that \(\Gamma_ 0\) is the set of all paths. In this paper it is shown that \(\Gamma_ 1\) is the class of proper interval graphs, and \(\Gamma_ 2\) the class of cocomparability graphs. From these characterizations there follows that all powers of proper interval graphs and of cocomparability graphs are again proper interval graphs and cocomparability graphs, respectively. Some additional results on proper powers of cocomparability graphs are also given, for instance these graphs have no induced subgraph isomorphic to \(K_{1,4}\) or \(K_{2,3}\).
0 references
distances
0 references
interval graphs
0 references
cocomparability graphs
0 references
powers
0 references