Menu
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 digraphs semi-connected digraphs 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 Hamiltonian cycles.