Path Matrices and Path Energies of Line Graphs

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.

Authors

Institutions

Publication Details

Journal
Scientific Annals of Computer Science
Published
2026-11-12
DOI
https://doi.org/10.47743/sacs.2027.1.1
Primary Topic
Graph theory and applications
Type
article
Field-Weighted Citation Impact
0.00
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
article

Path Matrices and Path Energies of Line Graphs

Amol P. Narke, Prashant Malavadkar
Scientific Annals of Computer Science
Graph theory and applications
article

Path Matrices and Path Energies of Line Graphs

Amol P. Narke, Prashant Malavadkar
article en

Abstract

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.

Scientific Annals of Computer ScienceVol. 37(1)
MIT World Peace University (IN)
Graph theory and applications
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon