Haemers’ Conjecture: An Algorithmic Perspective

Abstract

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.

KEYWORDS:

• generalized spectrum
• generalized spectral characterization
• generalized cospectral mates
• Smith normal form
• controllable graph

2020 MATHEMATICS SUBJECT CLASSIFICATION:

• 05C50

Acknowledgments

The authors are grateful to the referees for their careful reading and valuable comments.

Disclosure statement

The authors report there are no competing interests to declare.

Additional information

Funding

This work is supported by the National Natural Science Foundation of China (Grant Nos. 12001006, 12371357 and 11971406) and the Scientific Research Foundation of Anhui Polytechnic University (Grant No. 2019YQQ024).