Scholarlink

<p>The strong vertex (edge) span of a given graph <i>G</i> is the maximum distance that two players can maintain at all times while visiting all vertices (edges) of <i>G</i> 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.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

The Strong Vertex Span of Trees

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2025年6月3日

查看全文
  • Mateja Grašič,
  • Chris Mouron,
  • Andrej Taranenko

摘要

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.