On graphs whose orientations are determined by their Hermitian spectra (Q2200431)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On graphs whose orientations are determined by their Hermitian spectra |
scientific article |
Statements
On graphs whose orientations are determined by their Hermitian spectra (English)
0 references
21 September 2020
0 references
Summary: A mixed graph \(D\) is obtained from a simple graph \(G\), the underlying graph of \(D\), by orienting some edges of \(G\). A simple graph \(G\) is said to be ODHS (all orientations of \(G\) are determined by their \(H\)-spectra) if every two \(H\)-cospectral graphs in \(\mathcal{D}(G)\) are switching equivalent to each other, where \(\mathcal{D}(G)\) is the set of all mixed graphs with \(G\) as their underlying graph. In this paper, we characterize all bicyclic ODHS graphs and construct infinitely many ODHS graphs whose cycle spaces are of dimension \(k\). For a connected graph \(G\) whose cycle space is of dimension \(k\), we also obtain an achievable upper bound \(2^{2k-1} + 2^{k-1}\) for the number of switching equivalence classes in \(\mathcal{D}(G)\), which naturally is an upper bound of the number of cospectral classes in \(\mathcal{D}(G)\). To achieve these, we propose a valid method to estimate the number of switching equivalence classes in \(\mathcal{D}(G)\) based on the strong cycle basis, a special cycle basis introduced in this paper.
0 references
\(H\)-cospectral graphs
0 references
switching equivalence classes
0 references
strong cycle basis
0 references
0 references