Generalized spectral characterization of mixed graphs

DOI10.37236/9588zbMATH Open1472.05102arXiv1911.13004OpenAlexW3113616870MaRDI QIDQ2223447FDOQ2223447

Authors: Wei Wang, Lihong Qiu, Wei Wang, Jianguo Qian 

Publication date: 29 January 2021

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Abstract: A mixed graph $G$ is a graph obtained from a simple undirected graph by orientating a subset of edges. $G$ is self-converse if it is isomorphic to the graph obtained from $G$ by reversing each directed edge. For two mixed graphs $G$ and $H$ with Hermitian adjacency matrices $A(G)$ and $A(H)$, we say $G$ is $mathbbR$emph{-cospectral} to $H$ if, for any $yinmathbbR$, $yJ-A(G)$ and $yJ-A(H)$ have the same spectrum, where $J$ is the all-one matrix. A self-converse mixed graph $G$ is said to be determined by its generalized spectrum, if any self-converse mixed graph that is $R$-cospectral with $G$ is isomorphic to $G$. Let $G$ be a self-converse mixed graph of order $n$ such that $2^{-lfloorn/2floor}detW$ (which is always a real or pure imaginary Gaussian integer) is square-free in $mathbbZ[i]$, where $W=[e,Ae,ldots,A^{n-1}e]$, $A=A(G)$ and $e$ is the all-one vector. We prove that, for any self-converse mixed graph $H$ that is $mathbbR$-cospectral to $G$, there exists a Gaussian rational unitary matrix $U$ such that $Ue=e$, $U^{\ast }A(G)U=A(H)$ and $(1+i)U$ is a Gaussian integral matrix. In particular, if $G$ is an ordinary graph (viewed as a mixed graph) satisfying the above condition, then any self-converse mixed graph $H$ that is $mathbbR$-cospectral to $G$ is $G$ itself (in the sense of isomorphism). This strengthens a recent result of the first author.

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

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• Mixed paths and cycles determined by their spectrum
• Hermitian adjacency spectrum and switching equivalence of mixed graphs
• The \(k\)-generalized Hermitian adjacency matrices for mixed graphs
• On mixed graphs whose Hermitian spectral radii are at most 2
• Hermitian-adjacency matrices and Hermitian energies of mixed graphs

zbMATH Keywords

mixed graphgeneralized Hermitian spectrum

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)

Cites Work

• Practical graph isomorphism. II.
• Developments on spectral characterizations of graphs
• A note on cospectral graphs
• Which graphs are determined by their spectrum?
• A sufficient condition for a family of graphs being determined by their generalized spectra
• A new arithmetic criterion for graphs being determined by their generalized \(Q\)-spectrum
• A new method for constructing graphs determined by their generalized spectrum
• A simple arithmetic criterion for graphs being determined by their generalized spectra
• Generalized spectral characterization of graphs revisited
• An excluding algorithm for testing whether a family of graphs are determined by their generalized spectra
• Hermitian-adjacency matrices and Hermitian energies of mixed graphs
• Hermitian adjacency spectrum and switching equivalence of mixed graphs
• Discriminants of polynomials related to Chebyshev polynomials: the ``Mutt and Jeff syndrome
• On the generalized spectral characterizations of Eulerian graphs
• Mixed paths and cycles determined by their spectrum

Cited In (8)

• An improved condition for a graph to be determined by its generalized spectrum
• Proof of a conjecture on the determinant of the walk matrix of rooted product with a path
• Mixed paths and cycles determined by their spectrum
• Spectral characterizations of tournaments
• Self-converse mixed graphs are extremely rare
• Hermitian adjacency spectrum and switching equivalence of mixed graphs
• On graphs whose orientations are determined by their Hermitian spectra
• The negative tetrahedron and the first infinite family of connected digraphs that are strongly determined by the Hermitian spectrum

Uses Software

• SageMath
• MathOverflow

This page was built for publication: Generalized spectral characterization of mixed graphs

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