On graphs whose orientations are determined by their Hermitian spectra (Q2200431)

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.