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

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

收稿日期:2024-12-09 修回日期:2025-03-19 出版日期:2026-06-20 发布日期:2026-05-29
通讯作者: Andrej Taranenko, Email: andrej.taranenko@um.si E-mail:andrej.taranenko@um.si
作者简介:Mateja Gra?ič, Email: mateja.grasic@um.si;Chris Mouron, Email: mouronc@rhodes.edu
基金资助:
Mateja Grašič acknowledges the financial support from the Slovenian Research and Innovation Agency (research core funding No. P1-0288). Andrej Taranenko acknowledges the financial support from the Slovenian Research and Innovation Agency (research core funding No. P1-0297 and project N1-0285). All authors acknowledge the financial support from the Slovenian Research and Innovation Agency (project BI-US/22-24-121).

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

摘要： 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.

关键词: Strong vertex span, Strong edge span, Trees, Algorithm

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

中图分类号:

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.

[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

The Strong Vertex Span of Trees

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价