20.500.12556/DKUM-88137 Span of a graph keeping the safety distance Inspired by Lelek's idea from [Disjoint mappings and the span of spaces, Fund. Math. 55 (1964), 199 -- 214], we introduce the novel notion of the span of graphs. Using this, we solve the problem of determining the \emph{maximal safety distance} two players can keep at all times while traversing a graph. Moreover, their moves must be made with respect to certain move rules. For this purpose, we introduce different variants of a span of a given connected graph. All the variants model the maximum safety distance kept by two players in a graph traversal, where the players may only move with accordance to a specific set of rules, and their goal: visit either all vertices, or all edges. For each variant, we show that the solution can be obtained by considering only connected subgraphs of a graph product and the projections to the factors. We characterise graphs in which it is impossible to keep a positive safety distance at all moments in time. Finally, we present a polynomial time algorithm that determines the chosen span variant of a given graph. strong span of a graph direct span of a graph Cartesian span of a graph safety distance krepki razpon grafa direktni razpon grafa kartezični razpon grafa varnostna razdalja true true true Association DMTCS Angleški jezik Slovenski jezik Članek v reviji 2024-04-10 03:49:54 2024-06-07 11:06:53 2024-06-08 03:10:13 0000-00-00 00:00:00 2023 0 0 19 str. no. 1 Vol. 25 2023 0000-00-00 Zaloznikova Objavljeno NiDoloceno 2022-07-29 2023-02-19 2023-03-01 519.17 148408835 10.46298/dmtcs.9859 1365-8050 RAZ_Banic_Iztok_2023.pdf RAZ_Banic_Iztok_2023.pdf 1 1AA92015C783649B7951098931849AE4 b21413e5116d066aa0fab2edac9517fc8308a82a4474acfa52afff775254d373 5d30a70d-24ac-11ef-9523-00155d000105 https://dk.um.si/Dokument.php?lang=slv&id=180303 https://doi.org/10.46298/dmtcs.9859 0 a2bc092e-24ac-11ef-9523-00155d000105 https://dk.um.si/Dokument.php?lang=slv&id=180304 Fakulteta za naravoslovje in matematiko 0 0 0