论文标题
Haemers的猜想：算法观点
Haemers' conjecture: an algorithmic perspective
论文作者
论文摘要
通过它们的光谱表征图是光谱图理论中的一个基本且具有挑战性的问题，近年来，它受到了相当大的关注。在这一领域的主要未解决的猜想是Haemers的猜想，该猜想几乎所有图都由其光谱决定。尽管付出了很多努力，但到目前为止，这一猜想知之甚少。在本文中，我们将从算法的角度考虑haemers的猜想。根据图表的广义频谱特征的最新发展，我们提出了一种算法，以找到给定$ n $ vertex Graph $ g $的所有可能的广义骑士伴侣，假设$ g $是可控或几乎可以控制的。实验结果表明，对于大多数具有数十个顶点的图形，所提出的算法的运行速度令人惊讶。此外，我们在实验中观察到大多数图是由它们的广义光谱确定的，例如，在一个实验中，在50个顶点上所有随机生成的10,000个图表中，至少9945个图由它们的广义光谱确定。这些实验结果为Haemers的猜想提供了有力的证据。
Characterizing graphs by their spectra is a fundamental and challenging problem in spectral graph theory, which has received considerable attention in recent years. A major unsolved conjecture in this area is Haemers' conjecture which states that almost all graphs are determined by their spectra. Despite many efforts, little is known about this conjecture so far. In this paper, we shall consider Haemers' conjecture from an algorithmic perspective. Based on some recent developments in the generalized spectral characterizations of graphs, we propose an algorithm to find all possible generalized cospectral mates for a given $n$-vertex graph $G$, assuming that $G$ is controllable or almost controllable. The experimental results indicate that the proposed algorithm runs surprisingly fast for most graphs with several dozen vertices. Moreover, we observe in the experiment that most graphs are determined by their generalized spectra, e.g., at least 9945 graphs are determined by their generalized spectra among all randomly generated 10,000 graphs on 50 vertices in one experiment. These experimental results give strong evidence for Haemers' conjecture.
