On the Spectral Radius of the Maximum Degree Matrix of Graphs

Let G be a graph with n vertices, and let dG(u) denote the degree of vertex u in G. The maximum degree matrix MG of G is the square matrix of order n whose (u,v)-entry is equal to maxdG(u),dG(v) if vertices u and v are adjacent in G, and zero otherwise. Let Bp,q,r be the graph obtained from the complete graph Kp by removing an edge uv, and identifying vertices u and v with the end vertices u′ and v′ of the paths Pq and Pr, respectively. Let Gn,d denote the set of simple, connected graphs with n vertices and diameter d. A graph in Gn,d that attains the largest spectral radius of the maximum degree matrix is called a maximizing graph. In this paper, we first characterize the spectrum of the maximum degree matrix for graphs of the form Bn−i+2,i,d−i, where 1≤i≤⌊d2⌋. Furthermore, for d≥2, we prove that the maximizing graph in Gn,d is Bn−d+2,⌊d2⌋,⌈d2⌉. Finally, if d≥4 is an even integer, then the spectral radius of the maximum degree matrix in Bn−d+2,⌊d2⌋,⌈d2⌉ can be computed as the largest eigenvalue of a symmetric tridiagonal matrix of order d2+1.