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.

Signed Graphs with extremal least Laplacian eigenvalue / Belardo, Francesco; Zhou, Yue. - In: LINEAR ALGEBRA AND ITS APPLICATIONS. - ISSN 0024-3795. - 497:(2016), pp. 167-180. [10.1016/j.laa.2016.02.028]

Signed Graphs with extremal least Laplacian eigenvalue

BELARDO, Francesco;ZHOU, YUE
2016

Abstract

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.
2016
Signed Graphs with extremal least Laplacian eigenvalue / Belardo, Francesco; Zhou, Yue. - In: LINEAR ALGEBRA AND ITS APPLICATIONS. - ISSN 0024-3795. - 497:(2016), pp. 167-180. [10.1016/j.laa.2016.02.028]
File in questo prodotto:
File Dimensione Formato  
Signed Graphs with extremal least Laplacian eigenvalue.pdf

non disponibili

Descrizione: Documento in Post-print.
Tipologia: Documento in Post-print
Licenza: Accesso privato/ristretto
Dimensione 351.74 kB
Formato Adobe PDF
351.74 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

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/11588/632911
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 12
  • ???jsp.display-item.citation.isi??? 11
social impact