The strong vertex span of trees
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913603778510848 |
|---|---|
| author | Grašič, Mateja Mouron, Chris Taranenko, Andrej |
| author_facet | Grašič, Mateja Mouron, Chris Taranenko, Andrej |
| contents | 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 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_03266 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The strong vertex span of trees Grašič, Mateja Mouron, Chris Taranenko, Andrej Combinatorics Discrete Mathematics 05C05, 05C85 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 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. |
| title | The strong vertex span of trees |
| topic | Combinatorics Discrete Mathematics 05C05, 05C85 |
| url | https://arxiv.org/abs/2412.03266 |