Abstract
Since the introduction of the Hermitian adjacency matrix for digraphs, interest in so-called complex unit gain graphs has surged. In this work, we consider gain graphs whose spectra contain the minimum number of two distinct eigenvalues. Analogously to graphs with few distinct eigenvalues, a great deal of structural symmetry is required for a gain graph to attain this minimum. This allows us to draw a surprising parallel to well-studied systems of lines in complex space, through a natural correspondence to unit-norm tight frames. We offer a full classification of two-eigenvalue gain graphs with degree at most 4, or with multiplicity at most 3. Intermediate results include an extensive review of various relevant concepts related to lines in complex space, including SIC-POVMs, MUBs and geometries such as the Coxeter-Todd lattice, and many examples obtained as induced subgraphs by employing a technique parallel to the dismantling of association schemes. Finally, we touch on an innovative application of simulated annealing to find examples by computer. (c) 2022 The Author(s). Published by Elsevier B.V.This is an open access article under the CC BY-NC-ND license (http://creativecommons.org/licenses/by-nc-nd/4.0/).
Original language | English |
---|---|
Article number | 112827 |
Number of pages | 28 |
Journal | Discrete Mathematics |
Volume | 345 |
Issue number | 6 |
DOIs | |
Publication status | Published - Jun 2022 |
Keywords
- Complex unit gain graphs
- Spectrum
- Hermitian
- Equal-norm frames
- SIMULATED ANNEALING ALGORITHM
- STRONGLY REGULAR GRAPHS
- ASSOCIATION SCHEMES
- WEIGHING MATRICES
- SIGNED GRAPHS
- OPTIMIZATION
- CLASSIFICATION
- FRAMES
- SETS