Wednesday, 12 December 2007

soft question - Isn't a graph to be considered isomorphic to its complement, actually?

It is a strange question, but maybe a useful answer can make it a bit better.



Certainly for many purposes a graph will look totally different from its complement. For instance, a graph and its complement have completely different spectra, diameter, perfect matchings, etc. So that side of the question is kind-of lame, I agree.



On the other hand, for some purposes a graph is much the same as its complement. One obvious case is when you are interested in the automorphism group of a graph, or in the computational problem of graph isomorphism. Then you might as well think of a graph as a bicoloring of the edges of a complete graph. It then has a natural extra automorphism given by switching the two colors. More generally a colored graph with $n$ colors is equivalent, for graph isomorphism and graph automorphism questions, to a complete graph with $n+1$ colors. This viewpoint is more useful than you might first think, because a natural partial algorithm and preparatory step in the graph isomorphism and automorphism problems is to recolor every vertex by its valence, then color every edge by the colors of its vertices, etc., until the recoloring process stabilizes. Many graphs can be completely identified this way in practice. Recognizing the equivalence between a graph and its complement makes it easier to understand what these algorithms are really doing.



Even some specific graphs, such as the Higman-Sims graph, are mainly used for their automorphisms and similar purposes, and it might be better to think of them as colorings of a complete graph.



A much deeper example is the perfect graph theorem of Lovasz. The theorem is that a graph is perfect if only if its complement is perfect. For perfect graphs, taking the graph complement is closely related to the dual or polar polytope of a convex polytope.

No comments:

Post a Comment