Span of a Graph: Keeping the Safety Distance

DOI10.46298/DMTCS.9859arXiv2111.08980MaRDI QIDQ6131784FDOQ6131784

Publication date: 18 April 2024

Published in: Discrete Mathematics & Theoretical Computer Science (Search for Journal in Brave)

Abstract: 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.

Full work available at URL: https://arxiv.org/abs/2111.08980

Recommendations

zbMATH Keywords

safety distance Cartesian span of a graph direct span of a graph strong span of a graph

Mathematics Subject Classification ID

Distance in graphs (05C12) Games on graphs (graph-theoretic aspects) (05C57) Graph operations (line graphs, products, etc.) (05C76) Games involving graphs (91A43)

This page was built for publication: Span of a Graph: Keeping the Safety Distance

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6131784)