Graph isomorphism : Some special cases

Abstract

This paper investigates some special cases of graphs with a small number of vertices or edges where a characteristic property of the vertices and edges already determines the graph up to isomorphism. We also present counterexamples that show the limits of this approach to the graph isomorphism problem. The main interest in graph isomorphism for automated deduction lies in the fact that the problem of deciding whether a clause is a variant of another clause is a generalization of the graph isomorphism problem.