EUVIMEDEUVIMED entdecken
Crossref

Path Matrices and Path Energies of Line Graphs

Amol P. Narke, Prashant P. Malavadkar

Scientific Annals of Computer Science · 12.11.2026 · 37 (1) · 1

DOI: 10.47743/sacs.2027.1.1 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Scientific Annals of Computer Science, online erschienen am 12.11.2026. Verfasst von Amol P. Narke und 1 weiteren Autor:innen. Die Arbeit nennt 23 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Internally vertex-disjoint paths are a fundamental measure of connectivity in graphs and play a central role in the study of network robustness. The path matrix P(G) of a graph G on n vertices and m edges is the matrix whose (i, j)-entry equals the maximum number of internally vertex-disjoint paths between vertices vi and vj. In this paper, we initiate a systematic study of the path matrix and path energy of line graphs. For trees, an exact characterisation of the entries of the path matrix of the line graph in terms of vertex degrees is obtained, together with an explicit matrix formulation using the incidence matrix of the underlying tree. The following bounds are established for every tree T on n ≥ 3 vertices: 2(n − 2) ≤ PE(L(T)) ≤ (n − 1)(n − 2)3/2, with equality in the lower bound if and only if T ≅ Pn. For line graphs of star-like trees, we obtain a complete spectral decomposition of the path matrix and show that the path energy depends only on the number of arms and the total number of edges, and is invariant under redistribution of arm lengths. Finally, we adapt the standard vertex-splitting max-flow method to the line-graph setting and thereby obtain a polynomial-time procedure for computing the path matrix of the line graph of any connected graph.

Zitieren

APA

Narke, A. P., & Malavadkar, P. P. (2026). Path Matrices and Path Energies of Line Graphs. Scientific Annals of Computer Science, 37(1), 1. https://doi.org/10.47743/sacs.2027.1.1

Vancouver

Narke AP, Malavadkar PP. Path Matrices and Path Energies of Line Graphs. Scientific Annals of Computer Science. 2026;37(1):1. doi:10.47743/sacs.2027.1.1

BibTeX
@article{Narke2026,
  author = {Narke, Amol P. and Malavadkar, Prashant P.},
  title = {Path Matrices and Path Energies of Line Graphs},
  journal = {Scientific Annals of Computer Science},
  year = {2026},
  volume = {37},
  number = {1},
  pages = {1},
  doi = {10.47743/sacs.2027.1.1}
}
Kostenlos starten →