The negative tetrahedron and the first infinite family of connected digraphs that are strongly determined by the Hermitian spectrum

DOI10.1016/J.JCTA.2020.105232MaRDI QIDQ2306004zbMATH OpenOpenAlexFDO

Authors Pepijn Wissing, Edwin R. Van Dam

Publication date 20 March 2020

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/1903.09531

zbMATH Keywords

cospectral digraphsHermitian adjacency matrixspectra of digraphsspectral characterization of digraphs

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Connectivity (05C40) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Abstract: Thus far, digraphs that are uniquely determined by their Hermitian spectra have proven elusive. Instead, researchers have turned to spectral determination of classes of switching equivalent digraphs, rather than individual digraphs. In the present paper, we consider the traditional notion: a digraph (or mixed graph) is said to be strongly determined by its Hermitian spectrum (abbreviated SHDS) if it is isomorphic to each digraph to which it is cospectral. Convincing numerical evidence to support the claim that this property is extremely rare is provided. Nonetheless, the first infinite family of connected digraphs that is SHDS is constructed. This family is obtained via the introduction of twin vertices into a structure that is named negative tetrahedron. This special digraph, that exhibits extreme spectral behavior, is contained in the surprisingly small collection of all digraphs with exactly one negative eigenvalue, which is determined as an intermediate result.

Review text

It is very elusive to find digraphs that are uniquely determined by their Hermitian spectra. So, people usually turn to finding spectral determination of classes of switching equivalent digraphs, rather than individual digraphs. In the present paper, the authors return back to considering the traditional notion: the strongly determined digraph (or mixed graph) by its Hermitian spectrum (abbreviated SHDS), which is a digraph (or mixed graph) that is isomorphic to each digraph (or mixed graph) to which it is Hermitian cospectral. From numerical analysis (not a rigorous proof), they come to the conclusion that digraphs with this property are extremely rare. However, fortunately they can construct an infinite family of connected digraphs that is SHDS. This family is obtained via the introduction of twin vertices into a structure that is named negative tetrahedron. This special digraph, that exhibits extreme spectral behavior, is contained in the surprisingly small collection of all digraphs with exactly one negative eigenvalue, which is determined as an intermediate result.

Recommendations

• Generalized spectral characterization of mixed graphs
• Mixed paths and cycles determined by their spectrum
• Digraphs with Hermitian spectral radius below 2 and their cospectrality with paths
• A note on the spectral characterization of strongly connected bicyclic digraphs

Cites work

• A regularity lemma and twins in words
• Cyclotomic matrices over the Eisenstein and Gaussian integers
• Developments on spectral characterizations of graphs
• Digraphs with Hermitian spectral radius below 2 and their cospectrality with paths
• Enumeration of self‐converse digraphs
• Graph theory
• 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 510844 (Why is no real title available?)
• Interlacing eigenvalues and graphs
• Interlacing families and the Hermitian spectral norm of digraphs
• Laplacians and the Cheeger inequality for directed graphs
• Mixed graphs with \(H\)-rank 3
• Nullity of Hermitian-adjacency matrices of mixed graphs
• On the relation between theH-rank of a mixed graph and the matching number of its underlying graph
• On the Shannon capacity of a graph
• Relation between the \(H\)-rank of a mixed graph and the rank of its underlying graph
• Skew-adjacency matrices of graphs
• The Number of Linear, Directed, Rooted, and Connected Graphs
• The spectral distribution of random mixed graphs
• Using twins and scaling to construct cospectral graphs for the normalized Laplacian
• Which graphs are determined by their spectrum?

Cited in

(17)

• Spectral fundamentals and characterizations of signed directed graphs
• The spectra of digraphs with Morita equivalent C^-algebras
• 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
• Mixed graphs with smallest eigenvalue greater than \(- \frac{ \sqrt{ 5} + 1}{ 2} \)
• Self-converse mixed graphs are extremely rare
• Characterizing the mixed graphs with exactly one positive eigenvalue and its application to mixed graphs determined by their \(H\)-spectra
• On graphs whose orientations are determined by their Hermitian spectra
• Digraphs with Hermitian spectral radius below 2 and their cospectrality with paths
• On -gain graphs with few positive eigenvalues
• Mixed graphs whose Hermitian adjacency matrices of the second kind have the smallest eigenvalue greater than \(- \frac{3}{2}\)
• On the inertia index of a mixed graph in terms of the matching number
• The Hoffman program for mixed graphs
• Developments on the Hoffman program of 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: The negative tetrahedron and the first infinite family of connected digraphs that are strongly determined by the Hermitian spectrum

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