The Strong Vertex Span of Trees

doi:10.1007/s42967-025-00494-2

Communications on Applied Mathematics and Computation ›› 2026, Vol. 8 ›› Issue (3): 1157-1170.doi: 10.1007/s42967-025-00494-2

• ORIGINAL PAPERS • Previous Articles Next Articles

The Strong Vertex Span of Trees

Mateja Grašič^1,2, Chris Mouron³, Andrej Taranenko^1,2

1. Faculty of Natural Sciences and Mathematics, University of Maribor, Maribor, Slovenia;
2. Institute of Mathematics, Physics and Mechanics, Ljubljana, Slovenia;
3. Department of Mathematics and Statistics, Rhodes College, Memphis, TN, 38112, USA

Received:2024-12-09 Revised:2025-03-19 Online:2026-06-20 Published:2026-05-29
Contact: Andrej Taranenko, Email: andrej.taranenko@um.si E-mail:andrej.taranenko@um.si

Abstract

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.

Key words: Strong vertex span, Strong edge span, Trees, Algorithm

CLC Number:

05C05
05C85

Mateja Grašič, Chris Mouron, Andrej Taranenko. The Strong Vertex Span of Trees[J]. Communications on Applied Mathematics and Computation, 2026, 8(3): 1157-1170.

TrendMD

[1]	Zhengge Huang. New Gradient-Based Iterative-Like Algorithms for Solving a Class of Sylvester Tensor Equations [J]. Communications on Applied Mathematics and Computation, 2026, 8(3): 1005-1049.
[2]	Baoting Wang, Guoyu Zhang. A Fast H2N2 Finite Difference Scheme for the Fractional Sine-Gordon Equation [J]. Communications on Applied Mathematics and Computation, 2026, 8(2): 490-506.
[3]	Salman Ahmadi-Asl, Naeim Rezaeian, Ugochukwu O. Ugwu. Randomized Algorithms for Computing the Generalized Tensor SVD Based on the Tensor Product [J]. Communications on Applied Mathematics and Computation, 2026, 8(2): 605-621.
[4]	Bo Yu, Jiaxin Du, Xiaoxiao Qin. Fast Algorithms for Computing the Hilbert Transform of a Given Function with Cubic Splines [J]. Communications on Applied Mathematics and Computation, 2026, 8(1): 324-337.
[5]	Yu-Hang Li, Ju-Li Zhang. The Coefficient Estimation of Tensor Autoregression Based on TR Decomposition [J]. Communications on Applied Mathematics and Computation, 2025, 7(5): 1940-1958.
[6]	Gang Wu, Wen Yang. Joint Spectral Regression Methods for Large-Scale Discriminant Analysis [J]. Communications on Applied Mathematics and Computation, 2025, 7(5): 1791-1814.
[7]	Wenbin Gong, Yan Li, Yaqiang Wang. An Improved Iterative Algorithm for Identifying Strong H-Tensors [J]. Communications on Applied Mathematics and Computation, 2025, 7(4): 1598-1614.
[8]	Galina V. Muratova, Tatiana S. Martynova, Pavel A. Oganesyan. Numerical Solution of Partial Symmetric Generalized Eigenvalue Problems in Piezo Device Modal Analysis [J]. Communications on Applied Mathematics and Computation, 2025, 7(3): 1002-1015.
[9]	Jiachang Sun. GPA: Intrinsic Parallel Solver for the Discrete PDE Eigen-Problem [J]. Communications on Applied Mathematics and Computation, 2025, 7(3): 970-986.
[10]	Hao Lin, Cheng He. On Fixed-Parameter Solvability of the Minimax Path Location Problem [J]. Communications on Applied Mathematics and Computation, 2023, 5(4): 1644-1654.
[11]	Salman Ahmadi-Asl. An Efficient Randomized Fixed-Precision Algorithm for Tensor Singular Value Decomposition [J]. Communications on Applied Mathematics and Computation, 2023, 5(4): 1564-1583.
[12]	Xiaoyi Liu, Tingchun Wang, Shilong Jin, Qiaoqiao Xu. Two Energy-Preserving Compact Finite Difference Schemes for the Nonlinear Fourth-Order Wave Equation [J]. Communications on Applied Mathematics and Computation, 2022, 4(4): 1509-1530.
[13]	Ren-jun Qi, Zhi-zhong Sun. Some Numerical Extrapolation Methods for the Fractional Sub-diffusion Equation and Fractional Wave Equation Based on the L1 Formula [J]. Communications on Applied Mathematics and Computation, 2022, 4(4): 1313-1350.
[14]	H. Rehman, N. Chandra. Parametric Regression Approach for Gompertz Survival Times with Competing Risks [J]. Communications on Applied Mathematics and Computation, 2022, 4(4): 1175-1190.
[15]	Chacha Stephen Chacha. On Iterative Algorithm and Perturbation Analysis for the Nonlinear Matrix Equation [J]. Communications on Applied Mathematics and Computation, 2022, 4(3): 1158-1174.

The Strong Vertex Span of Trees

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

Comments