Pushing Vertices and Orienting Edges.
William F. Klostermeyer · 1999
A directed graph operation called pushing a vertex is studied. When a vertex is pushed, the orientation of each of its incident edges is reversed. We consider the problems of pushing vertices so as to produce strongly connected, semi-connected, and acyclic digraphs. NP-completeness results are shown for each problem. It is shown that it is possible to create a directed path between any two vertices in a digraph; additional positive results and characterizations are shown for tournaments, outerplanar digraphs, and Hamiltonian cycles. 1.