Signed Graphs with extremal least Laplacian eigenvalue.

A signed graph is a pair Γ = ( G , σ ) , where G = ( V ( G ) , E ( G ) ) is a graph and σ : E ( G ) → { + , − } is the corresponding sign function. For a signed graph we consider the Laplacian matrix defined as L ( Γ ) = D ( G ) − A ( Γ ) , where D ( G ) is the matrix of vertex degrees of G and 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 . Therefore, if Γ is not balanced, then λ 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. [ABSTRACT FROM AUTHOR]