# zbMATH — the first resource for mathematics

Domination on cocomparability graphs. (English) Zbl 0780.05032
A 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.

##### 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
Full Text: