Kernels and Quasi-kernels in Digraphs
Scott Heard · UVic’s Research and Learning Repository (University of Victoria) · 2005
Given a digraph D = (V, A), a quasi-kernel of D is an independent set Q C_ V such that for every vertex v not contained in Q, either there exists a vertex u E Q such that v dominates u, or there exists a vertex w such that v dominates w and w dominates some vertex u E Q.A sink in aIn this thesis we prove that if D is a semicomplete multipartite, quasi-transitive or locally semicomplete digraph that contains no sink, then D has two disjoint quasi-kernels.For a digraph D = (V, A) and a subset X V, pushing the set X means that we reverse the orientation of each arc with exactly one endpoint in X.In this thesis, we show that it is NP-complete to decide whether an arbitrary digraph D = (V, A) admits a subset X V such that after pushing X the resultant digraph contains no directed odd cycle.In addition we show that it is NP-hard to decide whether an arbitrary digraph D = (V, A) admits a subset X C V such that after pushing X the resultant digraph is kernel-perfect.Finally, we characterize, in terms of forbidden subdigraphs, multipartite tournaments M = (V, A) that contain a subset X 2 V for which pushing X results in a multipartite tournament that contains no odd cycle.