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.