2017/10/26 by Wenxue Du, Du, Wenxue
Engineering · Mathematics · #05C25 #05C50 #05C60 #Combinatorics (math.CO) #FOS: Mathematics #Finite Group Theory Research #Graph theory and applications #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.1710.09526
openalex publication_date 2017/10/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let G and H be two simple graphs. A bijection ϕ:V(G)→ V(H) is called an isomorphism between G and H if (ϕvi)(ϕvj)∈ E(H) ⇔ vi vj∈ E(G), ∀ vi,vj ∈ V(G). In the case that G = H, we say ϕ an automorphism of G and denote the group consisting of all automorphisms of G by Aut~G. As well-known, the problem of determining whether or not two given graphs are isomorphic is called Graph Isomorphism Problem (GI). One of key steps in resolving GI is to work out the partition Π^*G of V(G) composed of orbits of Aut~G. By means of geometric features of Π^*G and combinatorial constructions such as the multipartite graph [Π^*t1,⋯,Π^*ts], we can reduce the problem of determining ΠG^* to that of working out a series of partitions of V(G) each of which consists of orbits of a stabilizer that fixes a sequence of vertices of G, and thus the determination of the partition Π^*v is a critical transition. On the other hand, we have for a given subspace U ⊆ ℝn a permutation group Aut~U := \ σ∈ Sn : σ~ U = U \. As a matter of fact, Aut~G = ∩λ∈ spec A(G) Aut~Vλ, and moreover we can obtain a good approximation Π[ ⊕ Vλ ; v ] to Πv^* by analyzing a decomposition of Vλ resulted from the division of Vλ by subspaces \ proj[ Vλ ]( \pmbev )⊥ : v ∈ V(G) \. In fact, there is a close relation among subspaces spanned by cells of Π[ ⊕ Vλ ; v ] of G, which enables us to determine Πv^* more efficiently. In virtue of that, we devise a deterministic algorithm solving GI in time n O( log n ) .