Back to Search
Start Over
Span of a Graph: Keeping the Safety Distance
- Source :
- Discrete Mathematics & Theoretical Computer Science, Vol vol. 25:1, Iss Graph Theory (2023)
- Publication Year :
- 2023
- Publisher :
- Discrete Mathematics & Theoretical Computer Science, 2023.
-
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.
- Subjects :
- mathematics - combinatorics
05c60, 05c90
Mathematics
QA1-939
Subjects
Details
- Language :
- English
- ISSN :
- 13658050
- Volume :
- . 25:1
- Issue :
- Graph Theory
- Database :
- Directory of Open Access Journals
- Journal :
- Discrete Mathematics & Theoretical Computer Science
- Publication Type :
- Academic Journal
- Accession number :
- edsdoj.17a45b97e534ccc8bc73c9e825c2f11
- Document Type :
- article
- Full Text :
- https://doi.org/10.46298/dmtcs.9859