欢迎光临!
您现在所在的位置:首页 >> 通知公告 & 学术信息
学术信息
SEMINARS
The Graph Isomorphism Problem
时间  Datetime
2017-07-15 14:30 — 16:30 
地点  Venue
Middle Lecture Room
报告人  Speaker
Wenxue Du (杜文学)
单位  Affiliation
Anhui University
邀请人  Host
Yaokun Wu
报告摘要  Abstract

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