Generalized spectral characterization of mixed graphs

DOI10.37236/9588MaRDI QIDQ2223447zbMATH OpenOpenAlexFDO

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)

Copyright license Creative Commons Attribution 4.0 International

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

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

zbMATH Keywords

generalized Hermitian spectrummixed graph

Mathematics Subject Classification ID

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

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.

Review text

A mixed graph \(G\) is said to be strongly determined by its generalized Hermitian spectrum (abbreviated SHDGS), if, up to isomorphism, \(G\) is the unique mixed graph that is cospectral with \(G\) w.r.t. the generalized Hermitian spectrum. The authors conjecture that every such graph is SHDGS and prove that, for any mixed graph \(H\) that is cospectral with \(G\) w.r.t. the generalized Hermitian spectrum, there exists a Gaussian rational unitary matrix \(U\) with \(Ue = e\) such that \(U^\ast A(G)U = A(H)\) and \((1+i)U\) is a Gaussian integral matrix. The authors verify the conjecture in two extremal cases when \(G\) is either an undirected graph or a self-converse oriented graph. Consequently, the authors prove that all directed paths of even order are SHDGS.

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

Cites work

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

Cited in

(11)

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

Describes a project that uses

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)