Akademska digitalna zbirka SLovenije - logo
ALL libraries (COBIB.SI union bibliographic/catalogue database)
  • Span of a graph [Elektronski vir] : keeping the safety distance
    Banič, Iztok ; Taranenko, Andrej
    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.
    Source: Discrete mathematics & theoretical computer science [Elektronski vir]. - ISSN 1365-8050 (Vol. 25, no. 1, 2023, 19 str.)
    Type of material - e-article ; adult, serious
    Publish date - 2023
    Language - english
    COBISS.SI-ID - 148408835

    Link(s):

    Digital Library of the University of Maribor – DLUM

Shelf entry