Balancedness and the Least Laplacian Eigenvalue of Some Complex Unit Gain Graphs

Belardo, Francesco ; Brunetti, Maurizio ; Reff, Nathan

Discussiones Mathematicae. Graph Theory, Tome 40 (2020) no. 2, pp. 417-433

Résumé

Let 𝕋_4 = ±1, ±i be the subgroup of 4-th roots of unity inside 𝕋, the multiplicative group of complex units. A complex unit gain graph Φ is a simple graph Γ = (V(Γ) = v_1, . . ., v_n, E(Γ)) equipped with a map φ:E(Γ)→𝕋 defined on the set of oriented edges such that φ(v_iv_j) = φ(v_jv_i)^−1. The gain graph Φ is said to be balanced if for every cycle C = v_i_1v_i_2 . . . v_i_kv_i_1 we have φ(v_i_1v_i_2)φ(v_i_2v_i_3) . . . φ(v_i_kv_i_1) = 1. It is known that Φ is balanced if and only if the least Laplacian eigenvalue λ_n(Φ) is 0. Here we show that, if Φ is unbalanced and φ(Φ) ⊆ 𝕋_4, the eigenvalue λ_n(Φ) measures how far is Φ from being balanced. More precisely, let ν(Φ) (respectively, ∈(Φ)) be the number of vertices (respectively, edges) to cancel in order to get a balanced gain subgraph. We show that λ_n(Φ) ≤ ν(Φ) ≤ ∈(Φ). We also analyze the case when λ_n(Φ) = ν(Φ). In fact, we identify the structural conditions on Φ that lead to such equality.

Détail

Keywords: gain graph, Laplacian eigenvalues, balanced graph, algebraic frustration