The Strong Vertex Span of Trees

Abstract

The strong vertex (edge) span of a given graph G is the maximum distance that two players can maintain at all times while visiting all vertices (edges) of G and moving either to an adjacent vertex or staying in the current position independently of each other. We introduce the notions of switching walks and the triod size of a tree, which are used to determine the strong vertex and the strong edge span of an arbitrary tree. The obtained results are used in an algorithm that computes the strong vertex (edge) span of the input tree in linear time.

Keywords

Strong vertex span / Strong edge span / Trees / Algorithm

References

[1] BaničI, TaranenkoA. Span of a graph: keeping the safety distance. Discrete Math. Theor. Comput. Sci., 2023, 25: 1

[2] ErcegG, ŠubašićA, VojkovićT. Some results on the maximal safety distance in a graph. FILOMAT, 2023, 37155123-5136.

[3] LelekA. Disjoint mappings and the span of spaces. Fund. Math., 1964, 55: 199-214.

[4] ŠubašićA, VojkovićT. Vertex spans of multilayered cycle and path graphs. Axioms, 2024, 13: 236.

[5] Valiente, G.: Algorithms on Trees and Graphs. Springer-Verlag, Berlin, Heidelberg (2002)

Funding

Javna Agencija za Raziskovalno Dejavnost RS(P1-0288, BI-US/22-24-121)

RIGHTS & PERMISSIONS

The Author(s)