×

On \(m\)RJ reachability in trees. (English) Zbl 1282.91067

Summary: Given a tree \(T\), a configuration of \(T\) is denoted by 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 \(m\)RJ 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 \(m\)RJ moves (for some fixed \(m\)) in addition to simple moves. A tree is said to be \(m\)RJ reachable if there exists a configuration from which it is possible to take the robot to any vertex of the tree using simple or \(m\)RJ moves. A connected graph is 1RJ reachable. However, for \(m \geq 2\) there exists graphs that are not \(m\)RJ reachable. We characterize 2RJ and 3RJ reachable trees and give bound for the diameter of \(m\)RJ reachable trees.

MSC:

91A43 Games involving graphs
68R10 Graph theory (including graph drawing) in computer science
05C05 Trees
Full Text: DOI

References:

[1] Harary F., Graph Theory (1969)
[2] DOI: 10.1016/j.cor.2005.01.018 · Zbl 1086.90070 · doi:10.1016/j.cor.2005.01.018
[3] DOI: 10.1016/0304-3975(86)90146-5 · Zbl 0616.68064 · doi:10.1016/0304-3975(86)90146-5
[4] C. H. Papadimitriou, Foundations of Computer Science (1994) pp. 511–520.
[5] DOI: 10.1016/S0747-7171(08)80001-6 · Zbl 0704.68057 · doi:10.1016/S0747-7171(08)80001-6
[6] DOI: 10.1016/j.dam.2010.02.001 · Zbl 1230.05192 · doi:10.1016/j.dam.2010.02.001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.