2

It appears that there are some related questions on this forum. For example,

However, someone usually emphasizes a single invariant and its relationship with graph isomorphism, such as the spectrum.

What I want to ask is whether, if one invariant cannot determine it, we hope in combining multiple invariants, such as chromatic number, matching number, the number of orbits in the automorphism group, and so on. In other words, is there hope that the combination of invariants can achieve this? Common invariants can be found in the The House of Graphs , and we have included a screenshot below. enter image description here

How many invariants do we need to combine in order to determine whether two graphs are isomorphic? Or is this idea directly negative from the start? With the listed 40+ invariants from the screenshot, if they are all the same, is it possible to find two non-isomorphic graphs?

L.C. Zhang
  • 1,615

1 Answers1

4

There will be strongly-regular graphs of the same parameters with equal values of all those invariants. Since the parameters determine the eigenvalues, all the invariants determined by the spectrum (such as the spanning tree count) are determined. Most or all will be hamiltonian and traceable, and many have trivial group and equal chromatic number. If you want a specific example, the block-intersection graphs of Steiner triple systems are so numerous that it is impossible for them to all be determined by the invariants in this list.

Note that the concept of "invariant" is pretty general: any function on labelled graphs that is constant on isomorphism classes is included. A canonical labelling function is an example of an invariant that uniquely determines the graph up to isomorphism. The big question in this field is whether there is an invariant that distinguishes isomorphism classes and can be computed in polynomial time.

Brendan McKay
  • 37,203