University of York, Department of Computer Science

 

Graph Isomorphism and Cospectrality
Introduction Graph isomorphism is an interesting problem from an algorithmic perspective since it is one of a few problems which is not known to be either NP-complete or a P-problem. It is conjectured that the problem may be in its own complexity class, graph-isomorphism-complete. One efficient way of determining whether two graphs are the same is via the graph spectrum. If the spectra of two graphs are different, then they cannot be isomorphic. Most (and maybe all) types of spectra produce graphs which are not isomorphic but have the same spectra - these are called cospectral graphs. If there are no cospectral graphs, then we have an efficient solution to the graph isomorphism problem, i.e. it is a P-problem.

Cospectrality and representations

 The spectrum of a graph is the set of eigenvalues of a matrix representation of the graph. The number of cospectral graphs produced is highly dependent on the representation used. For example Haemers and Spence have looked at cospectrality for the adjacency matrix, the Laplacian and the signless Laplacian. We have extended this study to the normalised Laplacian.


Spectra can also be combined, to eliminate graphs which are not cospectral with respect to one of the combined representations. Graphs are then only cospectral if they are cospectral in all representations. If we combine the adjacency, Laplacian, signless Laplacian and normalised Laplacian, we find a total of 10096 cospectral graphs of size 10. In fact, the following matrix also produces the same 10096 spectral examples when used on its own:

The second-order matrix

seems to do better, at the expense of extra construction time, as we have found no graphs of size 11 or less cospectral in this matrix. However, all of these matrices are cospectral on strongly regular graphs (SRGs).

References

Strongly regular graphs

Strongly regular graphs cause problems for determining graphs by their spectra, since their spectra are strongly constrained (for example the adjacency matrix has exactly three unique eigenvalues). There exist large sets of SRGs with the same parameters (n,k,λ,μ) which are cospectral in all of the above matrices. Many are listed on Ted Spence's handy page.


It has proved possible to separate SRGs using spectra, by using inspiration from Quantum Mechanics, and in particular the quantum walk on the graph. The quantum walk is governed by the unitary matrix U (the equivalent of the transition matrix for random walks). U can be considered a representation of the graph, and will have complex eigenvalues. Because the walk is quantum, the properties are quite different to the random walk as walk amplitudes interfere with each other, and can be positive, negative or zero. SRGs are not distinguished by the spectrum of U; there are two key observations which allow us to separate using U. Firstly, sets of SRGs are constrained by the number of mutual neighbours (second order constraints) so we need to look at third-order structure to see any difference between the graphs. Secondly, we need to make use of the quantum amplitudes in some way. This leads us to consider

Sup+(U^3)

the positive support of the three-step quantum walk. We obtain the positve support by replacing all postive entries of U with 1 and all other entries with 0. There are no cospectral SRGs within the sets we have tested for this matrix, specifically the sets below.

(n,k,λ,μ) Number of SRGs (n,k,λ,μ) Number of SRGs
(16,6,2,2) 2 (35,18,9,9) 227
(16,9,4,6) 2 (36,14,4,6) 227
(25,12,6,4) 15 (36,15,6,6) 32548
(26,10,3,4) 10 (40,12,2,4) 28
(28,12,6,4) 4 (45,12,3,3) 78
(29,14,6,7) 41 (64,18,2,6) 167

This matrix does not separate all graphs, or even all regular graphs. We have found examples of size 14 4-regular graphs which are cospectral.

References