The least distance eigenvalue of the complements of graphs of diameter greater than three

Abstract

Suppose $G$ is a connected simple graph with the vertex set $V(G)=\{v_1,v_2,\cdots ,v_n\}$. Let $d_G(v_i,v_j)$ be the least distance between $v_i$ and $v_j$ in $G$. Then the distance matrix of $G$ is $D(G)=(d_{ij}{)}_{n\times n}$, where $d_{ij}=d_G(v_i,v_j)$. Since $D(G)$ is a non-negative real symmetric matrix, its eigenvalues can be arranged as ${\lambda }_1(G)\ge {\lambda }_2(G)\ge \cdots \ge {\lambda }_n(G)$, where eigenvalue ${\lambda }_n(G)$ is called the least distance eigenvalue of $G$. In this paper we determine the unique graph whose least distance eigenvalue attains maximum among all complements of graphs of diameter greater than three.

7 Pages, 0 figure