Edge-connectivity matrices and their spectra
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.].
- On graphs whose energy exceeds the number of vertices
- A sharp upper bound on the spectral radius of weighted graphs
- Extremal graph characterization from the bounds of the spectral radius of weighted graphs
- Sum-connectivity energy of graphs
- Bounds of the sum-connectivity energy of graphs.
- A note on upper bounds for the spectral radius of weighted graphs
- Exploring symmetries in cographs: obtaining spectra and energies
- Energy of matrices
- Positive and negative square energies of graphs
- On the spectral radius and energy of the weighted adjacency matrix of a graph
- Distance spectra of graphs: a survey
- Extremal Eigenvalues of Real Symmetric Matrices with Entries in an Interval
- Graph energy
- Graph theory
- scientific article; zbMATH DE number 47926 (Why is no real title available?)
- Maximal energy graphs
- Metric and ultrametric spaces of resistances
- Multi-Terminal Network Flows
- On path eigenvalues and path energy of graphs
- On the spectrum of an equitable quotient matrix and its application
- On the spread of certain normal matrices
- Path matrix and path energy of graphs
- The distance spectrum and energy of the compositions of regular graphs
- Uniformly connected graphs.
This page was built for publication: Edge-connectivity matrices and their spectra
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2668063)
