Domination on cocomparability graphs.

*(English)*Zbl 0780.05032A comparability graph is an undirected graph which admits an orientation which is transitive and antisymmetric. A cocomparability graph is the complement of a comparability graph. A dominating set (or total dominating set) in a graph \(G\) is a subset \(D\) of the vertex set \(V(G)\) of \(G\) such that for each \(x\in V(G)-D\) (or for each \(x\in V(G)\) respectively) there exists \(y\in D\) adjacent to \(x\). Various problems for cocomparability graphs and algorithms for solving them are studied. For a cocomparability graph the problem to determine a minimum independent dominating set and the problem to determine a minimum dominating set inducing a connected subgraph are proved to be solvable in the time \(O(n^ 3)\) and the problem to determine a minimum dominating set and the problem to determine a minimum total dominating set in the time \(O(n^ 6)\), while the problem to determine a minimum dominating set inducing a clique is proved to be NP-complete.

Reviewer: B.Zelinka (Liberec)

##### MSC:

05C35 | Extremal problems in graph theory |

68Q15 | Complexity classes (hierarchies, relations among complexity classes, etc.) |

68R10 | Graph theory (including graph drawing) in computer science |