Let Γ=(G,σ) be a connected signed graph, where G is the underlying simple graph and σ:E(G)→{1,−1} is the sign function on the edges of G. Let L(Γ)=D(G)−A(Γ), be the Laplacian of Γ and λ1\geqλ2\geq⋯\geqλn\geq0 be its eigenvalues. It is well-known that a signed graph Γ is balanced if and only if λn(Γ)=0. Here we show that, if Γ is unbalanced, then λn estimates how much Γ is far from being balanced. In particular, let ν(Γ) (resp. ϵ(Γ)) be the frustration number (resp. frustration index), that is the minimum number of vertices (resp. edges) to be deleted such that the signed graph is balanced. Then we prove that λn(Γ)\leq ν(Γ)\leq ϵ(Γ). Further we analyze the case when λn(Γ)=ν(Γ). In the latter setting, we identify the structure of the underlying graph G and we give an algebraic condition for L(Γ) which leads to the above equality.

Balancedness and the least eigenvalue of Laplacian of signed graphs

BELARDO, FRANCESCO
2014-01-01

Abstract

Let Γ=(G,σ) be a connected signed graph, where G is the underlying simple graph and σ:E(G)→{1,−1} is the sign function on the edges of G. Let L(Γ)=D(G)−A(Γ), be the Laplacian of Γ and λ1\geqλ2\geq⋯\geqλn\geq0 be its eigenvalues. It is well-known that a signed graph Γ is balanced if and only if λn(Γ)=0. Here we show that, if Γ is unbalanced, then λn estimates how much Γ is far from being balanced. In particular, let ν(Γ) (resp. ϵ(Γ)) be the frustration number (resp. frustration index), that is the minimum number of vertices (resp. edges) to be deleted such that the signed graph is balanced. Then we prove that λn(Γ)\leq ν(Γ)\leq ϵ(Γ). Further we analyze the case when λn(Γ)=ν(Γ). In the latter setting, we identify the structure of the underlying graph G and we give an algebraic condition for L(Γ) which leads to the above equality.
2014
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11570/2664987
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? 35
social impact