Eigenvalues of signed graphs

Abstract

Signed graphs have their edges labeled either as positive or negative. $\ddot{I}(M)$ denote the $M$-spectral radius of $\hat{I}\pounds$, where $M=M(\hat{I}\pounds )$ is a real symmetric graph matrix of $\hat{I}\pounds$. Obviously, $ρ(M)=\mbox{max}\{λ_1(M),-λ_n(M)\}$. Let $A(\hat{I}\pounds )$ be the adjacency matrix of $\hat{I}\pounds$ and $(K_n,H^{-})$ be a signed complete graph whose negative edges induce a subgraph $H$. In this paper, we first focus on a central problem in spectral extremal graph theory as follows: Which signed graph with maximum $\ddot{I}(A(\hat{I}\pounds ))$ among $(K_n,T^{-})$ where $T$ is a spanning tree? To answer the problem, we characterize the extremal signed graph with maximum $\hat{I}{»}_1(A(\hat{I}\pounds ))$ and minimum $\hat{I}{»}_n(A(\hat{I}\pounds ))$ among $(K_n,T^{-})$, respectively. Another interesting graph matrix of a signed graph is distance matrix, i.e. $D(\hat{I}\pounds )$ which was defined by Hameed, Shijin, Soorya, Germina and Zaslavsky [8]. Note that $A(\hat{I}\pounds )=D(\hat{I}\pounds )$ when $\hat{I}\pounds \in (K_n,T^{-})$. In this paper, we give upper bounds on the least distance eigenvalue of a signed graph $\hat{I}\pounds$ with diameter at least 2. This result implies a result proved by Lin [11] was originally conjectured by Aouchiche and Hansen [1].

18 pages, 2 figures