Graphs with large multiplicity of −2 in the spectrum of the eccentricity matrix

Abstract

The eccentricity matrix of a simple connected graph is obtained from the distance matrix by keeping only the entries that are largest in at least one of their row or column. This matrix can be seen as a counterpart to the standard adjacency matrix, since the latter one is also obtained from the distance matrix but this time by keeping only the entries equal to 1. It is known that, for λ∉{−1,0} and a fixed i∈N, when n passes N there is only a finite number of graphs with n vertices having λ as an eigenvalue of multiplicity n−i in the spectrum of the adjacency matrix. This phenomenon motivates us to consider graphs with large multiplicity of an eigenvalue of the eccentricity matrix. In this context, we determine all connected graphs with n vertices for which −2 has the multiplicity n−i, where i≤5. Infinite families of graphs with this spectral property are encountered. Results of this paper can be compared to results concerning graphs with large multiplicity of zero in the spectrum of the adjacency matrix; at present the graphs for which this multiplicity is n−i, where i≤4, are known. Our results also become meaningful in the framework of the median eigenvalue problem since, for sufficiently large n, the median eigenvalue of the obtained graphs is always −2.