Scholarlink

<p>In 1971, Graham and Pollak provided a formula for the determinant of the distance matrix of any tree on <i>n</i> vertices. Yan and Yeh reproved this by exploiting the fact that pendant vertices can be deleted from trees without changing the remaining entries of the distance matrix. Considering failures of their argument to generalize invites the question: which graphs have the property that deleting any one vertex results in a change to some pairwise distance? Such worst-case graphs are known as “distance critical”, and were first studied by Erdős and Howorka. This work explores the structural properties of distance critical graphs, preservation of distance-criticality by products, and the nature of extremal distance critical graphs. We end with a few open questions.</p>

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

Distance Critical Graphs

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2025年7月27日

查看全文
  • Joshua Cooper,
  • Gabrielle Tauscheck

摘要

In 1971, Graham and Pollak provided a formula for the determinant of the distance matrix of any tree on n vertices. Yan and Yeh reproved this by exploiting the fact that pendant vertices can be deleted from trees without changing the remaining entries of the distance matrix. Considering failures of their argument to generalize invites the question: which graphs have the property that deleting any one vertex results in a change to some pairwise distance? Such worst-case graphs are known as “distance critical”, and were first studied by Erdős and Howorka. This work explores the structural properties of distance critical graphs, preservation of distance-criticality by products, and the nature of extremal distance critical graphs. We end with a few open questions.