Spectral fundamentals and characterizations of signed directed graphs

DOI10.1016/J.JCTA.2021.105573MaRDI QIDQ2068613zbMATH OpenOpenAlexFDO

Authors Pepijn Wissing, Edwin R. Van Dam

Publication date 20 January 2022

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

Full work available at URL https://arxiv.org/abs/2009.12181

zbMATH Keywords

complex unit gain graphsHermitiansigned graphsspectra of digraphs

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Signed and weighted graphs (05C22) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)

Abstract: The spectral properties of signed directed graphs, which may be naturally obtained by assigning a sign to each edge of a directed graph, have received substantially less attention than those of their undirected and/or unsigned counterparts. To represent such signed directed graphs, we use a striking equivalence to $mathbb{T}_6$-gain graphs to formulate a Hermitian adjacency matrix, whose entries are the unit Eisenstein integers $exp(kpii/3),$ $kinmathbb{Z}_6.$ Many well-known results, such as (gain) switching and eigenvalue interlacing, naturally carry over to this paradigm. We show that non-empty signed directed graphs whose spectra occur uniquely, up to isomorphism, do not exist, but we provide several infinite families whose spectra occur uniquely up to switching equivalence. Intermediate results include a classification of all signed digraphs with rank $2,3$, and a deep discussion of signed digraphs with extremely few (1 or 2) non-negative (eq. non-positive) eigenvalues.

Recommendations

• On cospectral signed digraphs
• Open problems in the spectral theory of signed graphs
• On signed graphs with at most two eigenvalues unequal to \(\pm 1\)
• Spectra of signed graphs
• Quasicospectrality of graphs and digraph: a creative review

Cites work

• A group representation approach to balance of gain graphs
• A new kind of Hermitian matrices for digraphs
• Allow problems concerning spectral properties of sign pattern matrices: a survey
• Balancedness and the least eigenvalue of Laplacian of signed graphs
• Biased graphs. I: Bias, balance, and gains
• Characterization of graphs with exactly two non-negative eigenvalues
• Constructing cospectral signed graphs
• Cyclotomic matrices over the Eisenstein and Gaussian integers
• Developments on spectral characterizations of graphs
• Gain-line graphs via \(G\)-phases and group representations
• Hermitian adjacency spectrum and switching equivalence of mixed graphs
• Hermitian-adjacency matrices and Hermitian energies of mixed graphs
• scientific article; zbMATH DE number 1600999 (Why is no real title available?)
• scientific article; zbMATH DE number 3717357 (Why is no real title available?)
• Interlacing eigenvalues and graphs
• On the spectral characterization of kite graphs
• Oriented gain graphs, line graphs and eigenvalues
• Sign pattern matrices
• Signed graphs
• Spectral properties of complex unit gain graphs
• The negative tetrahedron and the first infinite family of connected digraphs that are strongly determined by the Hermitian spectrum
• Which graphs are determined by their spectrum?

Cited in

(23)

• The \(k\)-generalized Hermitian adjacency matrices for mixed graphs
• Hermitian adjacency matrix of the second kind for mixed graphs
• Unit gain graphs with two distinct eigenvalues and systems of lines in complex space
• Spectral characterizations of tournaments
• Spectral characterizations of signed lollipop graphs
• Quasicospectrality of graphs and digraph: a creative review
• On eigenspaces of some compound complex unit gain graphs
• On cospectral signed digraphs
• Open problems in the spectral theory of signed graphs
• The $ k $-${rm bf{ th}}$ spectral moment of signed complete graphs
• Spectral analysis of t-path signed graphs
• Mixed graphs whose Hermitian adjacency matrices of the second kind have the smallest eigenvalue greater than \(- \frac{3}{2}\)
• Characterizing signed mixed graphs with small eigenvalues
• A switching method for constructing cospectral gain graphs
• Construction of cospectral graphs, signed graphs and \(\mathbb{T}\)-gain graphs via partial transpose
• Turán problem of signed graph for negative odd cycle
• On signed graphs with at most three positive eigenvalues
• The Hoffman program for mixed graphs
• Symmetry in complex unit gain graphs and their spectra
• Unit dual quaternion directed graphs, formation control and general weighted directed graphs
• The largest eigenvalue of \(\mathcal{C}_k^-\)-free signed graphs
• Mixed graphs determined by their generalized Hermitian adjacency spectrum based on Eisenstein integers
• High-order spectral characterizations of graphs

This page was built for publication: Spectral fundamentals and characterizations of signed directed graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2068613)