SEMINARS
The Graph Isomorphism Problem

2017-07-15　14:30 — 16:30

Middle Lecture Room

Wenxue Du (杜文学)

Anhui University

Yaokun Wu

Let G and H be two simple graphs. A bijective map ?:V(G)→V(H) is called an isomorphism between G and H if ?(vi)?(vj)∈E(H) ⇔ vivj∈E(G) for any two vertices vi and vj of G, and G and H are said to be isomorphic if there exists such a map. In the case that G=H, we say ? an automorphism of G and denote the group consisting of automorphisms of G by AutG. One of key steps in determining whether or not G is isomorphic to H is to characterize the structure of the action of AutG on V(G). By means of bipartite graphs {[Π∗(u),Π∗(v)]:u,v∈V(G)} and other combinatorial constructions alike, we can reduce the problem of determining the partition Π∗G, composed of orbits of AutG, to that of working out the family of partitions {Π∗v:v∈V(G)}, where Π∗v is comprised of orbits of the stabilizer (AutG)v.

On the other hand, we have a permutation group AutU for each subspace U⊆Rn, which is composed of those permutations in Sn for each of which U is invariant. Then AutG=∩λ∈specA(G)AutVλ, where Vλ is the eigenspace of A(G) corresponding to λ. Accordingly, we can obtain the structure of AutG action by means of the structure of AutVλ action, λ∈specA(G). The latter can be obtained by analyzing a decomposition of Vλ resulted from the division of Vλ by subspaces {proj[Vλ](eev)⊥:v∈V(G)}, where proj[Vλ](eev)⊥ stands for the orthogonal complement of proj[Vλ](eev) in Vλ. As an application, we devise a new algorithm solving the Grap