کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4598833 | 1631107 | 2016 | 19 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: On the isomorphism of graphs having some eigenvalues of moderate multiplicity On the isomorphism of graphs having some eigenvalues of moderate multiplicity](/preview/png/4598833.png)
Graph Isomorphism is one of the most prominent problems in computer science, which is not known to be NP-complete or polynomial time solvable. Babai, Grigoryev, and Mount (STOC 1982) showed that for graphs, which only have eigenvalues of bounded multiplicity (except at most one eigenvalue), this problem is in P. Evdokimov and Ponomarenko (Combinatorica 1999) extended the result of Babai et al. to graphs for which all eigenvalues have multiplicity O(logn/loglogn)O(logn/loglogn), where n is the number of vertices. In this paper we present an elementary proof that if for two graphs the sum of squares of the multiplicities corresponding to the eigenvalues with unbounded multiplicity is O(logn/loglogn)O(logn/loglogn), then isomorphism testing can be solved in polynomial time. Although our result is completely covered by Evdokimov and Ponomarenko, and hence it is not new, our proof only uses elementary methods and is completely different from their considerably more demanding approach.
Journal: Linear Algebra and its Applications - Volume 488, 1 January 2016, Pages 377–395