Eigenvalues of signed graphs

MaRDI QIDQ6388506zbMATH OpenFDO

Authors Dan Li, Huiqiu Lin, Jixiang Meng

Publication date 17 January 2022

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)

Abstract: Signed graphs have their edges labeled either as positive or negative. $ho(M)$ denote the $M$-spectral radius of $Sigma$, where $M=M(Sigma)$ is a real symmetric graph matrix of $Sigma$. Obviously, $ho(M)=mboxmaxlambd{a}_1(M),-lambd{a}_n(M)$. Let $A(Sigma)$ be the adjacency matrix of $Sigma$ 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 $ho(A(Sigma))$ among $(K_n,T^{-})$ where $T$ is a spanning tree? To answer the problem, we characterize the extremal signed graph with maximum $lambd{a}_1(A(Sigma))$ and minimum $lambd{a}_n(A(Sigma))$ among $(K_n,T^{-})$, respectively. Another interesting graph matrix of a signed graph is distance matrix, i.e. $D(Sigma)$ which was defined by Hameed, Shijin, Soorya, Germina and Zaslavsky [8]. Note that $A(Sigma)=D(Sigma)$ when $Sigmain(K_n,T^{-})$. In this paper, we give upper bounds on the least distance eigenvalue of a signed graph $Sigma$ with diameter at least 2. This result implies a result proved by Lin [11] was originally conjectured by Aouchiche and Hansen [1].

This page was built for publication: Eigenvalues of signed graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6388506)