Some results on the maximal safety distance in a graph


Goran Erceg, Aljoša Šubašić, Tanja Vojković




The work in this paper is motivated by I. Banič and A. Taranenko's recent paper, where they introduced a new notion, the span of a graph. Their goal was to solve the problem of keeping the safety distance while two players are moving through a graph and they presented three different types of graph spans, depending on the movement rules. We observe the same goal, but give a different approach to that problem by directly defining the maximal safety distance for different movement rules two players can take. This allowed us to solve several problems, prove some relations between different graph spans, and calculate the span values for some classes of graphs.