On Cyclability And Strong Pushability In A Kind Of Graphs

Let G be a simple graph, and G^k be a simple graph on the same vertex set as G such that two vertices in G^k are adjacent if and only if they have distance at most k in G. Assume D be a digraph. A directed cycle C is a hamilton directed cycle if V(C) = V(D). A digraph D is hamiltonian if D contains a hamilton directed cycle. A digraph D is strongly connected(or, just strong) if, for every pair x, y of distinct vertices in D, there exists an x — y directed path and a, y — x directed path. Pushing a vertex v in a digraph reverses all the orientations of all arcs incident with v. We say that a digraph D can be pushed to a digraph H if a digraph isomorphic to H can be obtained by applying a sequence of pushes to D. A graph is said to cyclable if each of its orientations can be pushed to a hamiltonian digraph.Camion's theorem states that a tournament is strong if and only if it has a hamilton directed cycle. Klostermeyer proved that an orientation C² of the square of a cycle C can be made strong using the vertex push operation if and only if it can be made to have a hamilton directed cycle using the vertex push operation. In this paper, we will prove that an orientation P³ of the cube of a path P can be made strong using the push operation if and only if it can be made hamiltonian using the push operation. As a corollary, we get that 2^3n-6 - 2ⁿ of the possible 2^3n-6 orientations of the cube of a path, for n≥ 4, can be made to have a hamiltonian directed cycle (also can be made strong) using vertex pushes.