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

Full description

Saved in:
Bibliographic Details
Published in:Discrete mathematics and theoretical computer science 2023-01, Vol.25:1 (Graph Theory), p.1-19
Main Authors: Banič, Iztok, Taranenko, Andrej
Format: Article
Language:English
Subjects:
05c60, 05c90
Algorithms
Apexes
Graph theory
Graphs
mathematics - combinatorics
Players
Polynomials
Safety
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1365-8050
1365-8050
DOI:10.46298/dmtcs.9859