8 - Canonical star bases

Summary

We associate with an n-vertex graph a uniquely determined star basis of ℝⁿ which is canonical in the sense that two cospectral graphs are isomorphic if and only if they determine the same canonical star basis. Such a basis was introduced in [CvRSl] as a means of investigating the complexity of the graph isomorphism problem. Here we first present a polynomial algorithm [CvRS2] for constructing a star partition of G, and hence a corresponding star basis of ℝⁿ. Thereafter we describe a procedure, based on [CvRS2] and [Cve21], for constructing the canonical star basis, with emphasis on three special cases: graphs with distinct eigenvalues, graphs with bounded eigenvalue multiplicities, and strongly regular graphs. The approach provides an alternative proof of a result of Babai et al. [BaGM] that isomorphism testing for graphs with bounded eigenvalue multiplicities can be performed in polynomial time.

Since the material presented in this chapter is the subject of current research, changes and improvements to the procedure for constructing a canonical basis may well emerge in due course. The chapter is included nevertheless because it represents the original motivation for some of the work discussed earlier in the book.

Introduction

There are only finitely many star bases associated with a given graph G; for there are only finitely many star partitions of V(G), and if |V(G)| = n then each star partition determines n! star bases of ℝⁿ (one for each labelling of the vertices).