Edge-connectivity matrices and their spectra (Q2668063)

For any undirected graph \(G = (V,E)\) with non-negative edge weights, the edge-connectivity matrix \(C(G)\) of \(G\) is the \(V\times V\) matrix with diagonal entries equal to zero and off-diagonal entries \([C(G)]_{vw}\) equal to the minimum weight of any edge set whose deletion disconnects vertices \(v\) and \(w\). \textit{R. E. Gomory} and \textit{T. C. Hu} [J. Soc. Ind. Appl. Math. 9, 551--570 (1961; Zbl 0112.12405)] presented a simple and elegant result that precisely characterised when a non-negative symmetric matrix \(A\) is the edge-connectivity matrix \(C(G)\) of some graph \(G\), and they further proved that if \(A = C(G)\) for some graph \(G\), then \(A\) is indeed the edge-connectivity graph of a spanning tree \(T\) of \(G\): \(A = C(G) = C(T)\). The authors of the present paper study the spectrum of these matrices and prove tight lower and upper bounds on the smallest size of the eigenvalues \(\lambda_i\) of \(C(G)\) and of its energy \(\mathcal{E} = \sum |\lambda_i|\). In particular, they prove that \(-M\leq\lambda_i\), where \(M\) is the greatest edge weight, and that \(\mathcal{E}\leq 2(|V|-1)M\). This proves the edge analogue of an open conjecture regarding the energy of vertex-connectivity matrices of graphs, posed in [\textit{M. M. Shikare} et al., MATCH Commun. Math. Comput. Chem. 79, No. 2, 387--398 (2018; Zbl 1472.92340)]. Other interesting and important results are presented, including a generalisation of Gomory and Hu's characterisation [loc. cit.].