Balancedness and the Least Laplacian Eigenvalue of Some Complex Unit Gain Graphs
| Autor: | Maurizio Brunetti, Francesco Belardo, Nathan Reff |
|---|---|
| Přispěvatelé: | Belardo, Francesco, Brunetti, Maurizio, Reff, Nathan |
| Jazyk: | angličtina |
| Rok vydání: | 2020 |
| Předmět: |
balanced graph
Gain graph Applied Mathematics Balanced graph gain graph Laplacian eigenvalues Combinatorics gain graph Laplacian eigenvalues balanced graph algebraic frustration QA1-939 Discrete Mathematics and Combinatorics laplacian eigenvalues 05c22 algebraic frustration 05c50 Laplace operator Unit (ring theory) Eigenvalues and eigenvectors Mathematics |
| Zdroj: | Discussiones Mathematicae Graph Theory, Vol 40, Iss 2, Pp 417-433 (2020) |
| ISSN: | 2083-5892 |
| Popis: | Let $mathbb{T}_4={ pm 1, pm i}$ be the subgroup of $4$-th roots of unity inside $mathbb{T}$, the multiplicative group of complex units. A complex unit gain graph $Phi$ is a simple graph $Gamma=(V(Gamma)={v_1,dots, v_n},E(Gamma))$ equipped with a map $arphi : v {E}(Gamma) ightarrow mathbb{T}$ defined on the set of oriented edges such that $arphi(v_iv_j) = arphi(v_jv_i)^{-1}$. The gain graph $Phi$ is said to be balanced if for every cycle $C=v_{i_1}v_{i_2}cdots , v_{i_k}v_{i_1} $ we have $arphi(v_{i_1}v_{i_2})arphi(v_{i_2}v_{i_3}) , cdots , arphi(v_{i_{k}}v_{i_1})=1$.smallskip It is known that $Phi$ is balanced if and only if the least Laplacian eigenvalue $lambda_n(Phi)$ is $0$. Here we show that, if $Phi$ is unbalanced and $arphi (Phi) subseteq mathbb{T}_4$, the eigenvalue $lambda_n(Phi)$ measures how far is $Phi$ from being balanced. More precisely, let $ u(Phi)$ (resp., $epsilon(Phi)$) be the number of vertices (resp., edges) to cancel in order to get a balanced gain subgraph. We show that [lambda_n(Phi)leq u(Phi)leq epsilon(Phi).] We also analyze the case when $lambda_n(Phi)= u(Phi)$. In fact, we identify the structural conditions on $Phi$ that lead to such equality. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|