EUVIMEDEUVIMED entdecken
Crossref

Graphs with at most one Generalized Cospectral Mate

Wei Wang, Wei Wang, Tao Yu

The Electronic Journal of Combinatorics · 24.02.2023 · 30 (1)

DOI: 10.37236/10826 ↗

Kurz gefasst

Fachartikel in der Zeitschrift The Electronic Journal of Combinatorics, online erschienen am 24.02.2023. Verfasst von Wei Wang und 2 weiteren Autor:innen. Die Arbeit wurde bisher 4-mal zitiert (Crossref).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Let $G$ be an $n$-vertex graph with adjacency matrix $A$, and $W=[e,Ae,\ldots,A^{n-1}e]$ be the walk matrix of $G$, where $e$ is the all-one vector. In Wang [J. Combin. Theory, Ser. B, 122 (2017): 438-451], the author showed that any graph $G$ is uniquely determined by its generalized spectrum (DGS) whenever $2^{-\lfloor n/2 \rfloor}\det W$ is odd and square-free. In this paper, we introduce a large family of graphs$$\mathcal{F}_n=\{\text{$n$-vertex graphs~} G\colon\, 2^{-\lfloor n/2 \rfloor}\det W =p^2b\text{ and rank}W=n-1\text{ over } \mathbb{Z}/p\mathbb{Z}\},$$where $b$ is odd and square-free, $p$ is an odd prime and $p\nmid b$. We prove that any graph in $\mathcal{F}_n$ either is DGS or has exactly one generalized cospectral mate up to isomorphism. Moreover, we show that the problem of finding the generalized cospectral mate for a graph in $\mathcal{F}_n$ is equivalent to that of generating an appropriate rational orthogonal matrix from a given integral vector. This equivalence essentially depends on a surprising property of graphs in terms of generalized spectra, which states that any symmetric integral matrix generalized cospectral with the adjacency matrix of some graph must be an adjacency matrix. Based on this equivalence, we develop an efficient algorithm to decide whether a given graph in $\mathcal{F}_n$ is DGS and further to find the unique generalized cospectral mate when it is not. We give some experimental results on graphs with at most 20 vertices, which suggest that $\mathcal{F}_n$ may have a positive density (nearly $3\%$) and possibly almost all graphs in $\mathcal{F}_n$ are DGS as $n\rightarrow \infty$. This gives supporting evidence for Haemers' conjecture that almost all graphs are determined by their spectra.

Zitieren

APA

Wang, W., Wang, W., & Yu, T. (2023). Graphs with at most one Generalized Cospectral Mate. The Electronic Journal of Combinatorics, 30(1). https://doi.org/10.37236/10826

Vancouver

Wang W, Wang W, Yu T. Graphs with at most one Generalized Cospectral Mate. The Electronic Journal of Combinatorics. 2023;30(1). doi:10.37236/10826

BibTeX
@article{Wang2023,
  author = {Wang, Wei and Wang, Wei and Yu, Tao},
  title = {Graphs with at most one Generalized Cospectral Mate},
  journal = {The Electronic Journal of Combinatorics},
  year = {2023},
  volume = {30},
  number = {1},
  doi = {10.37236/10826}
}
Kostenlos starten →