کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4598744 | 1631098 | 2016 | 14 صفحه PDF | دانلود رایگان |
A signed graph is a pair Γ=(G,σ)Γ=(G,σ), where G=(V(G),E(G))G=(V(G),E(G)) is a graph and σ:E(G)→{+,−}σ:E(G)→{+,−} is the corresponding sign function. For a signed graph we consider the Laplacian matrix defined as L(Γ)=D(G)−A(Γ)L(Γ)=D(G)−A(Γ), where D(G)D(G) is the matrix of vertex degrees of G and A(Γ)A(Γ) 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λn=0. Therefore, if Γ is not balanced, then λn>0λ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.
Journal: Linear Algebra and its Applications - Volume 497, 15 May 2016, Pages 167–180