Geodesic
Balancedness and the Least Laplacian Eigenvalue of Some Complex Unit Gain Graphs
Discussiones Mathematicae. Graph Theory, Tome 40 (2020) no. 2, pp. 417-433.

Voir la notice de l'article provenant de la source Library of Science

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.
Keywords: gain graph, Laplacian eigenvalues, balanced graph, algebraic frustration 
@article{DMGT_2020_40_2_a4,
     author = {Belardo, Francesco and Brunetti, Maurizio and Reff, Nathan},
     title = {Balancedness and the {Least} {Laplacian} {Eigenvalue} of {Some} {Complex} {Unit} {Gain} {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {417--433},
     publisher = {mathdoc},
     volume = {40},
     number = {2},
     year = {2020},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2020_40_2_a4/}
}
TY  - JOUR
AU  - Belardo, Francesco
AU  - Brunetti, Maurizio
AU  - Reff, Nathan
TI  - Balancedness and the Least Laplacian Eigenvalue of Some Complex Unit Gain Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2020
SP  - 417
EP  - 433
VL  - 40
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2020_40_2_a4/
LA  - en
ID  - DMGT_2020_40_2_a4
ER  - 
%0 Journal Article
%A Belardo, Francesco
%A Brunetti, Maurizio
%A Reff, Nathan
%T Balancedness and the Least Laplacian Eigenvalue of Some Complex Unit Gain Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2020
%P 417-433
%V 40
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2020_40_2_a4/
%G en
%F DMGT_2020_40_2_a4
Belardo, Francesco; Brunetti, Maurizio; Reff, Nathan. Balancedness and the Least Laplacian Eigenvalue of Some Complex Unit Gain Graphs. Discussiones Mathematicae. Graph Theory, Tome 40 (2020) no. 2, pp. 417-433. http://geodesic.mathdoc.fr/item/DMGT_2020_40_2_a4/

[1] R.B. Bapat, D. Kalita and S. Pati, On weighted directed graphs, Linear Algebra Appl. 436 (2012) 99–111. doi:10.1016/j.laa.2011.06.035

[2] F. Belardo, Balancedness and the least eigenvalue of Laplacian of signed graphs, Linear Algebra Appl. 446 (2014) 133–147. doi:10.1016/j.laa.2014.01.001

[3] S. Fallat and Y.-Z. Fan, Bipartiteness and the least eigenvalue of signless Laplacian of graphs, Linear Algebra Appl. 436 (2012) 3254–3267. doi:10.1016/j.laa.2011.11.015

[4] K. Guo and B. Mohar, Hermitian adjacency matrix of digraphs and mixed graphs, J. Graph Theory 85 (2017) 217–248. doi:10.1002/jgt.22057

[5] R.A. Horn and C. R. Johnson, Matrix Analysis (Cambridge Univ. Press, New York, 2012). doi:10.1017/CBO9781139020411

[6] D. Kalita, Properties of first eigenvectors and first eigenvalues of nonsingular weighted directed graphs, Electron. J. Linear Algebra 30 (2015) 227–242. doi:10.13001/1081-3810.3029

[7] N. Reff, Spectral properties of complex unit gain graphs, Linear Algebra Appl. 436 (2012) 3165–3176. doi:10.1016/j.laa.2011.10.021

[8] N. Reff, Oriented gain graphs, line graphs and eigenvalues, Linear Algebra Appl. 506 (2016) 316–328. doi:10.1016/j.laa.2016.05.040

[9] Y.-Y. Tan and Y.Z. Fan, On edge singularity and eigenvectors of mixed graphs, Acta Math. Sin. (Engl. Ser.) 24 (2008) 139–146. doi:10.1007/s10114-007-1000-2

[10] Y. Wang, S.-C. Gong and Y.-Z. Fan, On the determinant of the Laplacian matrix of a complex unit gain graph, Discrete Math. 341 (2018) 81–86. doi:10.1016/j.disc.2017.07.003

[11] T. Zaslavsky, Biased graphs. I. Bias, balance, and gains, J. Combin. Theory Ser. B 47 (1989) 32–52. doi:10.1016/0095-8956(89)90063-4

[12] T. Zaslavsky, A mathematical bibliography of signed and gain graphs and allied areas, Electron. J. Combin. (1998) #DS8.