Signed Graphs with extremal least Laplacian eigenvalue

详细信息    查看全文

• 作者：Francesco Belardo^a ; ^{fbelardo@unina.it" class="auth_mail" title="E-mail the corresponding author} ; Yue Zhou^a ; ^b ; ^{yue.zhou.ovgu@gmail.com" class="auth_mail" title="E-mail the corresponding author}
• 关键词：05C50 ; 05C22
• 刊名：Linear Algebra and its Applications
• 出版年：2016
• 出版时间：15 May 2016
• 年：2016
• 卷：497
• 期：Complete
• 页码：167-180
• 全文大小：351 K

文摘

A signed graph is a pair Γ=(G,σ)$\mathrm{\Gamma }=(G,\sigma )$, where G=(V(G),E(G))$G=(V(G),E(G))$ is a graph and σ:E(G)→{+,−}$\sigma :E(G)\to \{+,-\}$ is the corresponding sign function. For a signed graph we consider the Laplacian matrix defined as L(Γ)=D(G)−A(Γ)$L(\mathrm{\Gamma })=D(G)-A(\mathrm{\Gamma })$, where D(G)$D(G)$ is the matrix of vertex degrees of G   and A(Γ)$A(\mathrm{\Gamma })$ is the (signed) adjacency matrix. It is well-known that Γ is balanced, that is, each cycle contains an even number of negative edges, if and only if the least Laplacian eigenvalue λ_n=0${\lambda }_n=0$. Therefore, if Γ is not balanced, then 5c57d32f472316d6" title="Click to view the MathML source">λ_n>0${\lambda }_n>0$. We show here that among unbalanced connected signed graphs of given order the least eigenvalue is minimal for an unbalanced triangle with a hanging path, while the least eigenvalue is maximal for the complete graph with the all-negative sign function.