ON mRJ REACHABILITY IN TREES
Biswajit Deb, Kalpesh Kapoor, Sukanta Pati · Discrete Mathematics Algorithms and Applications · 2012
Given a tree T, a configuration of T is denoted by [Formula: see text] which represents that there is a robot at the vertex u, a hole at the vertex v and obstacles in the remaining vertices of T. By an mRJ move we mean that the robot is moved from the vertex u to a vertex v having a hole by jumping over m obstacles along a path. The case m = 0 is a simple move of taking the robot from u to the adjacent vertex v with a hole. We investigate the problem of moving a robot from its initial position to all the other vertices using mRJ moves (for some fixed m) in addition to simple moves. A tree is said to be mRJ reachable if there exists a configuration from which it is possible to take the robot to any vertex of the tree using simple or mRJ moves. A connected graph is 1RJ reachable. However, for m ≥ 2 there exists graphs that are not mRJ reachable. We characterize 2RJ and 3RJ reachable trees and give bound for the diameter of mRJ reachable trees.