Information Technology Reference
In-Depth Information
Chapter 11
Permutation Groups and the Graph
Isomorphism Problem
Sumanta Ghosh and Piyush P Kurur
Abstract
In this article we discuss various algorithms for permutation group-
theoretic problems and their connections to Graph Isomorphism. In the last part
we examine the group representability problem on graphs, its connection to Graph
Isomorphism, and discuss some open problems that arise in this context.
ยท
Keywords
Graph isomorphism
Permutation groups
11.1 Introduction
One of the core ideas in mathematics is the notion of an isomorphism, i.e. structure
preserving bijections between mathematical objects like groups, rings and fields.
A natural computational question is to decide, given two such objects as input,
whether they are isomorphic or not. In the context of undirected finite graphs, this
problem is called the graph isomorphism problem and is the subject matter of this
article. Informally, we say that two graphs are isomorphic if they are the same up
to a renaming of their vertices, i.e. we have a bijection between the vertex sets that
preserve the adjacency relation of edges. Many other isomorphism problems for
explicitly presented finite mathematical structures like groups, for example, reduce
to the graph isomorphism problem. Also, many problems that arise in practice, like
studying the structure of chemical compounds, are essentially graph isomorphism in
disguise. Hence, understanding this problem computationally is important.
