Scholarlink

The path matrix and path energy of a graph provide valuable insights into structural properties related to vertex-disjoint paths. In this paper, we present a new algorithm for computing the all-pairs path matrix of undirected graphs. The method employs Gomory-Hu trees with fast unit-capacity max-flow computations, achieving a time complexity of \(O(|V|\,|E|\sqrt{|E|} + |V|^2)\) . We further establish new bounds for the path energy in terms of the maximum degree and the Frobenius norm, which improve upon the existing bound of \(2(n-1)^2\) and give sharper estimates for all non-complete graphs. In addition, we demonstrate a connection between classical graph energy and path energy, thereby contributing to the broader framework of spectral graph theory.

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

An Efficient Algorithm for Path Matrix Computation and Improved Path Energy Bounds

  • 会议论文

  • 发表日期：

    2026年

查看全文
  • Amol P. Narke,
  • Prashant P. Malavadkar

摘要

The path matrix and path energy of a graph provide valuable insights into structural properties related to vertex-disjoint paths. In this paper, we present a new algorithm for computing the all-pairs path matrix of undirected graphs. The method employs Gomory-Hu trees with fast unit-capacity max-flow computations, achieving a time complexity of \(O(|V|\,|E|\sqrt{|E|} + |V|^2)\) . We further establish new bounds for the path energy in terms of the maximum degree and the Frobenius norm, which improve upon the existing bound of \(2(n-1)^2\) and give sharper estimates for all non-complete graphs. In addition, we demonstrate a connection between classical graph energy and path energy, thereby contributing to the broader framework of spectral graph theory.