Pósa Rotation
A Pósa rotation is an operation on a graph path used in the study of Hamiltonian paths and Hamiltonian cycles. Let
| P=(v_0,v_1,...,v_l) |
(1)
|
be a path in a graph G. If the endpoint v_l is adjacent to v_i for some 0<=i<l-1, then replacing the edge v_iv_(i+1) by v_iv_l and reversing the terminal subpath gives the new path
| P^'=(v_0,v_1,...,v_i,v_l,v_(l-1),...,v_(i+1)). |
(2)
|
The vertex v_i is called the pivot of the rotation, the endpoint v_0 remains fixed, and the other endpoint changes from v_l to v_(i+1).
Repeated Pósa rotations preserve the vertex set of the path while producing many possible endpoints. Together with steps that extend a path to a new vertex or close it into a cycle, these rotations form the Pósa rotation-extension technique, a standard tool in Hamiltonicity arguments, especially for random graphs.
For a longest path P in G, let R(P) be the set of endpoints obtainable from P by a finite sequence of Pósa rotations with one endpoint fixed. Pósa's lemma states that the external neighborhood N(R(P)), consisting of the vertices outside R(P) adjacent to a vertex of R(P), satisfies
| |N(R(P))|<=2|R(P)|-1 |
(3)
|
(Pósa 1976).
See also
Hamiltonian Cycle, Hamiltonian Path, Longest Path, Pósa's Theorem, Random GraphExplore with Wolfram|Alpha
References
Pósa, L. "Hamiltonian Circuits in Random Graphs." Disc. Math. 14, 359-364, 1976. https://doi.org/10.1016/0012-365X(76)90068-6.Cite this as:
Weisstein, Eric W. "Pósa Rotation." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/PosaRotation.html