×

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
PDF BibTeX XML Cite
Full Text: DOI