Geodesic
Testing isomorphism of central Cayley graphs over almost simple groups in polynomial time
Zapiski Nauchnykh Seminarov POMI, Problems in the theory of representations of algebras and groups. Part 31, Tome 455 (2017), pp. 154-180 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

A Cayley graph over a group $G$ is said to be central if its connection set is a normal subset of $G$. It is proved that for any two central Cayley graphs over explicitly given almost simple groups of order $n$, the set of all isomorphisms from the first graph onto the second can be found in time $\mathrm{poly}(n)$. 
@article{ZNSL_2017_455_a12,
     author = {I. Ponomarenko and A. Vasil'ev},
     title = {Testing isomorphism of central {Cayley} graphs over almost simple groups in polynomial time},
     journal = {Zapiski Nauchnykh Seminarov POMI},
     pages = {154--180},
     year = {2017},
     volume = {455},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/ZNSL_2017_455_a12/}
}
TY  - JOUR
AU  - I. Ponomarenko
AU  - A. Vasil'ev
TI  - Testing isomorphism of central Cayley graphs over almost simple groups in polynomial time
JO  - Zapiski Nauchnykh Seminarov POMI
PY  - 2017
SP  - 154
EP  - 180
VL  - 455
UR  - http://geodesic.mathdoc.fr/item/ZNSL_2017_455_a12/
LA  - en
ID  - ZNSL_2017_455_a12
ER  - 
%0 Journal Article
%A I. Ponomarenko
%A A. Vasil'ev
%T Testing isomorphism of central Cayley graphs over almost simple groups in polynomial time
%J Zapiski Nauchnykh Seminarov POMI
%D 2017
%P 154-180
%V 455
%U http://geodesic.mathdoc.fr/item/ZNSL_2017_455_a12/
%G en
%F ZNSL_2017_455_a12
I. Ponomarenko; A. Vasil'ev. Testing isomorphism of central Cayley graphs over almost simple groups in polynomial time. Zapiski Nauchnykh Seminarov POMI, Problems in the theory of representations of algebras and groups. Part 31, Tome 455 (2017), pp. 154-180. http://geodesic.mathdoc.fr/item/ZNSL_2017_455_a12/

[1] L. Babai, W. Kantor, E. M. Luks, “Computational complexity and the classification of finite simple groups”, Proceedings of the 24th Ann. Symp. Found. Comput. Sci., 1983, 162–171

[2] J. Bray, J. Holt, D. Roney-Dougal, The Maximal Subgroups of the Low-Dimensional Finite Classical Groups, Cambridge University Press, Cambridge, 2013 | MR | Zbl

[3] P. J. Cameron, Permutation Groups, Cambridge University Press, 1999 | MR | Zbl

[4] J. H. Conway, R. T. Curtis, S. P. Norton, R. A. Parker, R. A. Wilson, An ATLAS of Finite Groups, Oxford University Press, Oxford, 1985 | MR

[5] F. Dalla Volta, A. Lucchini, “Generation of almost simple groups”, J. Algebra, 178:1 (1995), 194–223 | DOI | MR | Zbl

[6] S. Evdokimov, I. Ponomarenko, “Recognizing and isomorphism testing circulant graphs in polynomial time”, Algebra Analiz, 15:6 (2003), 1–34 | MR | Zbl

[7] S. Evdokimov, I. Ponomarenko, “Permutation group approach to association schemes”, Eur. J. Combin., 30 (2009), 1456–1476 | DOI | MR | Zbl

[8] S. Evdokimov, I. Ponomarenko, “Schurity of $S$-rings over a cyclic group and generalized wreath product of permutation groups”, Algebra Analiz, 24:3 (2012), 84–127 | MR | Zbl

[9] A. Ganesan, “Automorphism group of the complete transposition graph”, J. Algebr. Combin., 42:3 (2015), 793–801 | DOI | MR | Zbl

[10] C. H. Li, “On isomorphisms of finite Cayley graphs – a survey”, Discrete Math., 256 (2002), 301–334 | DOI | MR | Zbl

[11] M. W. Liebeck, Ch. E. Praeger, J. Saxl, Regular subgroups of primitive permutation groups, Memoirs Amer. Math. Soc., 203, no. 952, 2010, 88 pp. | DOI | MR

[12] E. M. Luks, “Isomorphism of graphs of bounded valence can be tested in polynomial time”, J. Comp. Sys. Sci., 25 (1982), 42–65 | DOI | MR | Zbl

[13] M. Muzychuk, “A solution of the isomorphism problem for circulant graphs”, Proc. London Math. Soc., 88 (2004), 1–41 | DOI | MR | Zbl

[14] I. Ponomarenko, “Bases of Schurian antisymmetric coherent configurations and isomorphism test for Schurian tournaments”, J. Math. Sci., 192:3 (2013), 316–338 | DOI | MR | Zbl

[15] B. Weisfeiler (editor), On Construction and Identification of Graphs, Lecture Notes Math., 558, 1976 | DOI | Zbl

[16] H. Wielandt, Finite Permutation Groups, Academic press, New York–London, 1964 | MR | Zbl

[17] H. Wielandt, Permutation Groups Through Invariant Relations and Invariant Functions, Lect. Notes, Dept. Math. Ohio St. Univ., Columbus, 1969