On Eigenvalues and Main Eigenvalues of a Graph

Mirko Lepović

Mathematica Moravica, Tome 4 (2000) no. 1.

Résumé

Let $G$ be a simple graph of order $n$ and let $\lambda_{1}\geq \lambda_{2}\geq \cdots \geq\lambda_{n}$ and $\lambda_{1}^{\ast}\geq\lambda_{2}^{\ast}\cdots \geq\lambda_{n}^{\ast}$ be its eigenvalues with respect to the ordinary adjacency matrix $A=A(G)$ and the Seidel adjacency matrix $A^{\ast}=A^{\ast}(G)$, respectively. Using the Courant-Weyl inequalities we prove that $\bar{\lambda}_{n+1-i}\in [-\lambda_{i}-1,-\lambda_{i+1}-1]$ and $\lambda_{n+1-i}^{\ast}\in [-2\lambda_{i}-1,-2\lambda_{i+1}-1]$ for $i=1,2,\dots,n-1$, where $\bar{\lambda}_{i}$ are the eigenvalues of its complement $\bar{G}$. Besides, if $G$ and $H$ are two switching equivalent graphs, the we find $\lambda_{i}(G)\in[\lambda_{i+1}(H),\lambda_{i-1}(H)]$ for $i=2,3,\dots,n-1$. Next, let $\mu_{1},\mu_{2},\dots,\mu_{k}$ and $\bar{\mu}_{1},\bar{\mu}_{2},\dots,\bar{\mu}_{k}$ denote the main eigenvalues of the graph $G$ and the complementary graph $\bar{G}$, respectively. In this paper we also prove $\sum_{i=1}^{k}(\mu_{i}+\bar{mu}_{i}) = n-k$.

Détail

Mots-clés : Graph, eigenvalue, main eigenvalue