Finding minimum dominating cycles in permutation graphs (Q1060966)

A dominating cycle for a graph \(G=(V,E)\) is a subset C of V which has the following properties: (i) the subgraph of G induced by C has a Hamiltonian cycle, and (ii) every vertex of V is adjacent to some vertex of C. In this paper, we develop an \(O(n^ 2)\) algorithm for finding a minimum cardinality dominating cycle in a permutation graph. We also show that a minimum cardinality dominating cycle in a permutation graph always has an even number of vertices unless it is isomorphic to \(C_ 3\).