Edge-connectivity matrices and their spectra

The edge-connectivity matrix of a weighted graph is the matrix whose off-diagonal $v$-$w$ entry is the weight of a minimum edge cut separating vertices $v$ and $w$. Its computation is a classical topic of combinatorial optimization since at least the seminal work of Gomory and Hu. In this article, we investigate spectral properties of these matrices. In particular, we provide tight bounds on the smallest eigenvalue and the energy. Moreover, we study the eigenvector structure and show in which cases eigenvectors can be easily obtained from matrix entries. These results in turn rely on a new characterization of those nonnegative matrices that can actually occur as edge-connectivity matrices.


Introduction
For an undirected graph G = (V, E) with nonnegative edge weights its edgeconnectivity matrix is the V ×V matrix C(G) whose off-diagonal v-w entry denotes the minimum weight of an edge set whose removal disconnects the vertices v and w. The diagonal entries are defined as zero. In the seminal article [5], Gomory and Hu show that there exists a weighted tree T = (V, F ) on the same vertex set as G, but not necessarily with F ⊆ E, such that C(T ) = C(G). Even stronger, for each pair of vertices v and w the two sides of a minimum cut that separates v and w in T also induce a minimum cut that separates v and w in G. An auxiliary result of Gomory and Hu, which is particularly important for our investigation, is a characterization of those matrices that can occur as edge-connectivity matrices of Our considerations about the spectrum of the edge-connectivity matrix are inspired by recent articles that investigate the spectrum of the vertex-connectivity matrix or path matrix P (G) of an unweighted graph G = (V, E). This is the V ×V matrix whose off-diagonal v-w entry is the maximum number of independent v-w paths with only zeros on the diagonal. Shikare and coauthors [14] raised the conjecture that the energy of P (G), that is the sum of the absolute values of the eigenvalues, is at most 2(n − 1) 2 . Ilić and Bašić [9] claim to prove this bound by employing the approach of Koolen and Moulton [10]. However, following their arguments carefully, they only obtain an upper bound of (n−1) 5/2 +(n−1) 3/2 , which is strictly larger than (n − 1) 2 for all n ∈ N. Nevertheless, our numerical investigations have not yet revealed any counterexamples to the stated bound. An analogous result for the edge-connectivity matrix is presented in Item (i) of Theorem 1.1. In another article [13], Patekar and Shikare claim that P (G) + D(G) is positive semidefinite, where D(G) denotes the diagonal matrix of vertex degrees. This would immediately imply the conjecture about the energy. However, the claim that P (G) + D(G) is positive semidefinite is indeed false. A counter example is given by the graph G in Figure 1 for which
It appears rather natural to consider also the related problem where the number of independent paths is replaced by the number of edge-disjoint paths or, what is the same, edge cuts. The preceding equivalence is the edge version of Menger's theorem [12], which, for instance, is presented by Diestel [3, Section 3]. It turns out that the aforementioned assertions are both true for the edge-connectivity matrix and even stronger statements hold.
the maximum off-diagonal entry in row v and by M := max{c vw : v, w ∈ V } the maximum entry of C. Then the following statements hold.
(iii) The energy of C is at most 2(n − 1)M with equality if and only if G is uniformly M-edge-connected.
Note that Item (i) comprises the result that C(G)+D(G) is positive semidefinite for any graph G because all v, w ∈ V (G) satisfy c vw ≤ min{deg(v), deg(w)} and thus also m(v) ≤ deg(v) is true for all v ∈ V (G). Proofs for the items of Theorem 1.1 are given in the subsequent sections in a more general setting.
Basic properties of the edge-connectivity matrix are also investigated by Akbari and coauthors [1]. They determine the spectrum of bicyclic graphs and consider the structure of uniformly k-edge-connected graphs. These are graphs in which k ∈ N is the maximum number of edge-disjoint paths between any two vertices. Analogously, a graph is called uniformly k-connected if k ∈ N is the maximum number of independent paths between any two vertices. More about the structure of these graph classes can be found in Göring, Hofmann, and Streicher [7]. Also note that there are results on the largest eigenvalue ̺ of vertex-connectivity matrices. Shikare and coauthors [14] show that (n − 1) ≤ ̺ ≤ (n − 1) 2 for a graph on n vertices by using Perron-Frobenius arguments, which are presented comprehensively by Horn and Johnson [8,Chapter 8]. Both bounds are tight. They are attained for trees or complete graphs, respectively. Moreover, the same arguments and obtained bounds hold analogously for edge-connectivity matrices.
Outline. In Section 2, we present an alternative characterization of edge-connectivity matrices. We use these results in Section 3 to prove spectral bounds and eigenvector properties. Finally, Section 4 provides an alternative interpretation of our results for distance matrices whose entries satisfy an ultrametric.
We conclude this introduction with further notation that is particularly important for our investigation. All vectors and matrices in this article are indexed by some finite set V or V × V , respectively, and we write n = |V | for short. For a subset of and 0 otherwise. In other words, J X = 1 X 1 ⊤ X . By 1 we mean the all ones vector, for J V we occasionally write J for short and I is the identity matrix. Furthermore, we denote V × V diagonal matrices whose diagonal entries are given by a sequence (x v ) v∈V by diag(x v : v ∈ V ). The vectors of the standard basis of R V are denoted by e v for v ∈ V . For a symmetric matrix C with eigenvalues λ 1 , . . . , λ n its energy E(C) is defined as E(C) = n i=1 |λ i |. An overview about methods and different variants of the energy concept is given by Li, Shi, and Gutman in the monograph [11]. By an equitable partition of a matrix C we mean a partition of C into submatrices where each block C ij has constant row sums equal to q ij . The matrix Q = (q ij ) is called an equitable quotient matrix of C and all eigenvalues of Q are also eigenvalues of C. You and coauthors [16] provide details about the structure of such matrices. Lastly, for graph theoretical terminology we refer to Diestel [3].

Characterizing edge-connectivity matrices
To begin, we recall the following characterization that is due to Gomory and Hu [5].

only zeros on its diagonal occurs as an edge-connectivity matrix of a weighted graph if and only if it satisfies the Gomory-Hu triangle inequality
Our characterization is in terms of the following property.

Definition 2.2.
For a real symmetric V ×V matrix C = (c vw ) and a real number ℓ we denote by Both the Gomory-Hu triangle inequality as well as the terraced structure make perfect sense without any assumptions on nonnegativity. So we formulate the next theorem for arbitrary symmetric matrices.

Theorem 2.3.
For a real symmetric V × V matrix C the following statements are equivalent.
(i) The matrix C is terraced.
(ii) The matrix C satisfies the Gomory-Hu triangle inequality for all x, y, z ∈ V .
Proof. We show first that (i) implies (ii). So let C be terraced and define T (ℓ) as in Definition 2.2. We choose x, y, z ∈ V without loss of generality such that min{c xy , c yz } = c yz =: ℓ, in other words c xy ≥ c yz ≥ ℓ. Then there is a set X in T (ℓ) with (x, y) ∈ X × X, which means that x, y ∈ X. Likewise, there is a set X ′ with y, z ∈ X ′ . Because z ∈ X ∩ X ′ , we obtain that X = X ′ , as the sets in T (ℓ) are defined to be pairwise disjoint. We observe that x, y, z ∈ X and in particular (x, z) ∈ X × X which implies c xz ≥ ℓ, as desired.
We show that (ii) implies (i) by induction on n := |V |. For n = 1 there is nothing to show. So let n > 1 and define L := min{c vw : v, w ∈ V }. Suppose that the column with index z contains an entry equal to L and define two sets X and Y by For x ∈ X and y ∈ Y it follows that c xz ≤ c yz = c zy and equality can only hold if Y = {z} and c zz = L. Applying the Gomory-Hu triangle inequality twice, we obtain that The last equality deserves a word of explanation. If y = z, then c xz < c yz , as otherwise x / ∈ X. Thus for the preceding inequality to hold, the last minimum must be equal to c xy . If y = z, the last equality follows from c zz ≥ c xz , which is true by the assumption in (ii). In both cases, we obtain that c xy = c xz = L for an arbitrary pair (x, y) ∈ X × Y .
So we observe that all entries of C restricted to X × Y and Y × X are equal to L.
The restrictions C| X×X and C| Y ×Y of C to X × X and Y × Y , respectively, satisfy the triangle inequality and, by induction, are terraced. Because S L (C) = V and we conclude that C is of the desired form.
In the specific case of an edge-connectivity matrix C of a graph G on n vertices, we know by the results of Gomory and Hu [5] that such a matrix can have at most n − 1 different values for its off-diagonal entries. Thus a terraced matrix can have at most 2n − 1 distinct values.

Spectral properties of terraced matrices
With the structural results of the previous section at hand, we proceed with spectral investigations, which enable us to resolve the claims from Theorem 1.1. Proof. Let 0 ≤ ℓ 0 < · · · < ℓ k be the distinct values of entries of a real nonnegative terraced matrix C. With the notation of Definition 2.2, we can write C as This is a nonnegative linear combination of positive semidefinite matrices which is why C is positive semidefinite as well. Some eigenvalues and eigenvectors of terraced matrices can be read off from row maxima directly. In particular, we easily obtain the smallest eigenvalue in case of a nonnegative terraced matrix.

Proof of Item
Theorem 3.2. Let C = (c vw ) be a real symmetric matrix whose off-diagonal entries satisfy the Gomory-Hu triangle inequality and let x, y ∈ V with x = y.
Then the value c xy is maximal among the off-diagonal elements in its row and column and c xx = c yy if and only if e x −e y is an eigenvector of C with corresponding eigenvalue c xx − c xy .
Proof. First, let x, y ∈ V with x = y satisfy c xx = c yy and let c xy = c yx be a maximum off-diagonal entry in its row and column. As C satisfies the Gomory-Hu triangle inequality, we obtain for each z ∈ V with z = x and z = y that This implies that c xz = c yz . As a consequence, and thus e x − e y is an eigenvector for c xx − c xy .
Conversely, let e x −e y be an eigenvector of C with corresponding eigenvalue c xx −c xy for some x, y ∈ V . Then the eigenequation (C(e x − e y )) z = c zx − c zy = 0 for z ∈ V with z = x and z = y implies that c zx = c zy . Because C is symmetric it follows that c xz = c zy = min{c xz , c zy } ≤ c xy by the Gomory-Hu triangle inequality. Hence, c xy is the maximum off-diagonal entry in its row and column. Furthermore, as c xx − c xy is an eigenvalue of C with eigenvector e x − e y , the eigenequation (C(e x − e y )) y = c yx − c yy = c xy − c xx implies that c xx = c yy , as desired.
Proof of Item (ii) of Theorem 1.1. Let C = (c vw ) be the edge-connectivity matrix of a weighted graph. Then C is nonnegative with only zeros on its diagonal and its off-diagonal entries satisfy the Gomory-Hu triangle inequality by Theorem 2.1. Elements x, y ∈ V (G) with c xy = M := max{c vw : v, w ∈ V } satisfy the conditions of Theorem 3.2 and so c xx − c xy = −M is an eigenvalue of C. Moreover, by Theorem 2.3, MI + C is a nonnegative terraced matrix all of whose eigenvalues are nonnegative according to Theorem 3.1. So −M is indeed the smallest eigenvalue of C.
The energy bound (iii) of Theorem 1.1 follows directly from the following more general statement. Theorem 3.3. Let C be a real nonnegative symmetric matrix whose off-diagonal entries satisfy the Gomory-Hu triangle inequality with n rows and columns and only zeros on its diagonal. Then the energy of C is at most 2(n − 1)M, where M := max{c vw : v, w ∈ V }. Furthermore, M(J − I) is the only such matrix that attains this bound.
Proof. Because the trace of C is zero, the energy of C is twice the sum of the absolute values of the negative eigenvalues. This sum is at most (n − 1) times the absolute value of the smallest eigenvalue which by Theorem 3.2 is −M.
It is an easy computation that the matrix M(J − I) attains the bound. Furthermore, it is a consequence of the Perron-Frobenius theory that any other matrix whose entries are bounded from above by M has a largest eigenvalue strictly less than (n−1)M. So M(J −I) is indeed the only matrix which attains the bound.
In terms of graph theory, the preceding energy bound is attained if and only if we are given a uniformly M-edge-connected graph. In the remainder of this section, we refine our results on the eigenvector structure of edge-connectivity matrices and achieve a lower bound for the energy. (ii) If x 1 ∼ x 2 and y 1 ∼ y 2 , then c x 1 y 1 = c x 2 y 2 or, equivalently, an entry c xy depends only on the equivalence classes of x and y.
(iii) Let X 1 , . . . , X k be the equivalence classes with respect to the relation ∼ and assume further that the diagonal entries satisfy c xx = c yy whenever x ∼ y.
(iv) Assume in addition to (iii) that C is nonnegative and has only zeros on its diagonal. Denote further by m(X i ) the common value m(x) for x ∈ X i . Then This inequality is an equality if and only if the equitable quotient matrix Q has no negative eigenvalues.
Proof. We begin with Item (i). The relation ∼ is reflexive by definition. It is symmetric because C is. As for transitivity assume that x ∼ y and y ∼ z. Hence For Item (ii), let x 1 ∼ x 2 and y 1 ∼ y 2 . This means that c x 1 x 2 is the maximum entry in rows x 1 and x 2 . Likewise, c y 1 y 2 is the maximum entry in rows y 1 and y 2 . By applying the Gomory-Hu triangle inequality and the symmetry of C repeatedly, we obtain that We observe that all inequalities in this chain are indeed equalities and consequently c x 1 y 1 = c x 2 y 2 , as desired.
For Item (iii), note that Item (ii) provides us with the fact that the submatrices C| X i ×X j are constant for i, j ∈ V with i = j. This implies in particular that their row sums are constant. Similarly, for i ∈ V all off-diagonal entries of C| X i ×X i have the same value by the definition of the relation ∼ and thus all diagonal entries have the same value by assumption. The stated formula for the entries q ij is a direct consequence.
We finally turn to Item (iv). Let X = {x 1 , . . . , x s } be an equivalence class with respect to the relation ∼. Then we obtain s − 1 linearly independent eigenvectors e x 1 − e x i for i = 2, . . . , s with a corresponding eigenvalue −m(X) ≤ 0. This contributes −(s − 1)m(X) to the sum of the negative eigenvalues. Therefore, summation over all classes, contributes to E(C). From the partition of V into equivalence classes X 1 , . . . , X k , we obtain in total |V | − k nonpositive eigenvalues, when counting multiplicities. The corresponding linearly independent eigenvectors are of the form e x − e y where x ∼ y.
The remaining k eigenvectors in an eigenbasis can be chosen orthogonal on the aforementioned vectors. This means, they can be chosen constant on the classes X i or, equivalently, of the form The corresponding eigenequation CZ = λZ is equivalent to Qz = λz, where z = (z 1 , . . . , z k ) ⊤ . This shows that the remaining k eigenvalues of C, in particular the positive ones, are among the eigenvalues of Q. This provides us with the relation E(C) = E(Q) + trace(Q) which in turn implies the bound to be shown, as clearly E(Q) ≥ trace(Q) with equality if and only if all eigenvalues of Q are nonnegative.
Corollary 3.5. The equitable quotient matrix Q from the previous theorem is similar to the symmetric matrix Q ′ = (q ′ ij ) with If Q ′ is positive semidefinite, the inequality in the previous theorem is an equality.
From X 1 we obtain three eigenvalues −4 with linearly independent eigenvectors e 1 − e 2 , e 2 − e 3 , e 3 − e 4 and X 2 provides us with an eigenvalue −3 corresponding to the eigenvector e 5 − e 6 . A lower bound on the energy is therefore Theorem 3.4 also tells us that this lower bound is not tight, because Q has another negative eigenvalue, as its determinant is −36. However, the achieved value is quite close to the actual energy of 15 + 3 √ 41 ≈ 34.21.

Ultrametric distance matrices
The structure of distance matrices of graphs is an active research topic. See Aouchiche and Hansen [2] for an overview or Stevanović and Indulal [15] for results on the distance energy. Most of the studies in that field involve shortest paths distances, whereas our results shed light on the spectral properties of ultrametric distance matrices. To see that, consider a graph G and its edge-connectivity matrix C = (c vw ) and define for two vertices v, w ∈ V (G) the distance d(v, w) := (c vw ) −1 .
Then the strong triangle inequality d(x, z) ≤ max{d(x, y), d(y, z)} holds for all x, y, z ∈ V (G). See also Gurvich [6] for how this metric is some kind of resistance distance. Many of the results of the previous section have analogues in this setting. Indeed, if the entries of a matrix D arise from an ultrametric, then −D satisfies the Gomory-Hu triangle inequality and all of our previous results that do not require a nonnegativity assumption hold for −D as well. We state those results for completeness, occasionally with a slightly different wording. (ii) The matrix D induces an equivalence relation on V by x ∼ y :⇔ x = y or r(x) = r(y) = d(x, y).
(iii) If x 1 ∼ x 2 and y 1 ∼ y 2 , then d(x 1 , y 1 ) = d(x 2 , y 2 ) or, equivalently, d(x, y) depends only on the equivalence classes of x and y, respectively.
(iv) Let X 1 , . . . , X k be the equivalence classes with respect to the relation ∼ and denote by r(X i ) the common value r(x) of x ∈ X i . Then the restrictions (v) The energies of D and its equitable quotient matrix Q are related by We also have a lower bound on the smallest eigenvalue of an ultrametric distance matrix, which essentially relies on the following result of Zhan [17,Therorem 1] for general symmetric interval matrices.
where the inequalities are meant componentwise. Then the only optimal solution of problem (P1) up to simultaneous permutations of rows and columns is

This bound is attained if and only if there is a bipartition
Equivalently, the stated bound is attained if and only if D = X * − mI, where X * is defined as in Theorem 4.2.
Proof. We recall first that if d is an ultrametric, then d(x, x) = 0 for all x ∈ V . Consequently, D has only zeros on its diagonal. Thus the optimal value of the problem to minimize λ n (X) such that m(J − I) ≤ X ≤ M (J − I) is certainly a lower bound for the smallest eigenvalue of an ultrametric matrix. Now, if X is an optimal solution of problem (P2), then X +mI is a feasible solution of problem (P1) and thus opt(P2) + m ≥ opt(P1). Conversely, by Theorem 4.2, X * +mI is an optimal solution of problem (P1) and X * is feasible for problem (P2). Consequently, opt(P1) − m ≥ opt(P2), as desired. The stated bound on the smallest eigenvalue follows directly from Theorem 4.2 and the fact that the unique optimal solution to (P2) is an ultrametric matrix.

Conclusions and related problems
Motivated by the recent interest in the spectra of vertex-connectivity matrices, we found even stronger structural properties for the edge-connectivity matrix. Note that both problems, the issue of whether the energy of a vertex-connectivity matrix of a graph on n vertices is bounded from above by 2(n − 1) 2 as well as the question for a tight lower bound on its smallest eigenvalue, are still open.
Furthermore, we obtained that for edge-connectivity matrices the upper bound (n − 1) 2 on the largest eigenvalue as well as the lower bound −(n − 1) on the smallest eigenvalue are attained simultaneously by the matrix that arises from the complete graph. This provides us with a tight upper bound (n − 1)(n − 2) on the spread of such matrices, which is defined as the largest distance between any two eigenvalues of a matrix. This resolves a special case of an intriguing open problem stated by Zhan [17,Problem 2] for which Fallat and Xing [4] formulated a detailed conjecture. There, the question for the spread is stated for general symmetric interval matrices. Note, however, that our result on the spread is bound to the very rich structure of edge-connectivity matrices. In different settings, one might not expect to find a matrix that attains an upper bound on the largest eigenvalue and a lower bound on the smallest eigenvalue simultaneously.