Circulant graphs: recognizing and isomorphism testing in polynomial time

Evdokimov, S.; Ponomarenko, I.

doi:10.1090/S1061-0022-04-00833-7

Circulant graphs: recognizing and isomorphism testing in polynomial time
HTML articles powered by AMS MathViewer

by S. A. Evdokimov and I. N. Ponomarenko
Translated by: the authors

St. Petersburg Math. J. 15 (2004), 813-835

DOI: https://doi.org/10.1090/S1061-0022-04-00833-7

Published electronically: November 16, 2004

PDF | Request permission

Abstract:

An algorithm is constructed for recognizing the circulant graphs and finding a canonical labeling for them in polynomial time. This algorithm also yields a cycle base of an arbitrary solvable permutation group. The consistency of the algorithm is based on a new result on the structure of Schur rings over a finite cyclic group.

References

L. Babai and E. M. Luks, Canonical labeling of graphs, Annual ACM Symposium on Theory of Computing (Proc. 15th Annual ACM Symposium on Theory of Computing), ACM Press, New York, NY, 1983, pp. 171–183.
Garrett Birkhoff, Lattice theory, 3rd ed., American Mathematical Society Colloquium Publications, Vol. XXV, American Mathematical Society, Providence, R.I., 1967. MR 0227053
A. E. Brouwer, A. M. Cohen, and A. Neumaier, Distance-regular graphs, Ergebnisse der Mathematik und ihrer Grenzgebiete (3) [Results in Mathematics and Related Areas (3)], vol. 18, Springer-Verlag, Berlin, 1989. MR 1002568, DOI 10.1007/978-3-642-74341-2
John D. Dixon and Brian Mortimer, Permutation groups, Graduate Texts in Mathematics, vol. 163, Springer-Verlag, New York, 1996. MR 1409812, DOI 10.1007/978-1-4612-0731-3
S. Evdokimov, M. E. Muzychuk, I. Ponomarenko, and G. Tinhofer, Recognizing certain Cayley graphs in polynomial time (submitted to Electron. J. Combin.).
S. A. Evdokimov and I. N. Ponomarenko, Two inequalities for the parameters of a cellular algebra, Zap. Nauchn. Sem. S.-Peterburg. Otdel. Mat. Inst. Steklov. (POMI) 240 (1997), no. Teor. Predst. Din. Sist. Komb. i Algoritm. Metody. 2, 82–95, 292 (Russian, with English and Russian summaries); English transl., J. Math. Sci. (New York) 96 (1999), no. 5, 3496–3504. MR 1691640, DOI 10.1007/BF02175828
Sergei Evdokimov and Ilia Ponomarenko, Isomorphism of coloured graphs with slowly increasing multiplicity of Jordan blocks, Combinatorica 19 (1999), no. 3, 321–333. MR 1723252, DOI 10.1007/s004930050059
Sergei Evdokimov, Marek Karpinski, and Ilia Ponomarenko, On a new high-dimensional Weisfeiler-Lehman algorithm, J. Algebraic Combin. 10 (1999), no. 1, 29–45. MR 1701282, DOI 10.1023/A:1018672019177
Sergei Evdokimov and Ilia Ponomarenko, Separability number and Schurity number of coherent configurations, Electron. J. Combin. 7 (2000), Research Paper 31, 33. MR 1763969, DOI 10.37236/1509
S. A. Evdokimov and I. N. Ponomarenko, On a family of Schur rings over a finite cyclic group, Algebra i Analiz 13 (2001), no. 3, 139–154 (Russian, with Russian summary); English transl., St. Petersburg Math. J. 13 (2002), no. 3, 441–451. MR 1850191
S. A. Evdokimov and I. N. Ponomarenko, Characterization of cyclotomic schemes and normal Schur rings over a cyclic group, Algebra i Analiz 14 (2002), no. 2, 11–55 (Russian, with Russian summary); English transl., St. Petersburg Math. J. 14 (2003), no. 2, 189–221. MR 1925880
D. G. Higman, Coherent configurations. I, Rend. Sem. Mat. Univ. Padova 44 (1970), 1–25. MR 325420
Ka Hin Leung and Shing Hing Man, On Schur rings over cyclic groups. II, J. Algebra 183 (1996), no. 2, 273–285. MR 1399027, DOI 10.1006/jabr.1996.0220
Cai Heng Li, On isomorphisms of finite Cayley graphs—a survey, Discrete Math. 256 (2002), no. 1-2, 301–334. MR 1927074, DOI 10.1016/S0012-365X(01)00438-1
Anna Lubiw, Some NP-complete problems similar to graph isomorphism, SIAM J. Comput. 10 (1981), no. 1, 11–21. MR 605600, DOI 10.1137/0210002
Eugene M. Luks, Permutation groups and polynomial-time computation, Groups and computation (New Brunswick, NJ, 1991) DIMACS Ser. Discrete Math. Theoret. Comput. Sci., vol. 11, Amer. Math. Soc., Providence, RI, 1993, pp. 139–175. MR 1235801, DOI 10.1090/dimacs/011/11
Mikhail E. Muzychuk, On the structure of basic sets of Schur rings over cyclic groups, J. Algebra 169 (1994), no. 2, 655–678. MR 1297167, DOI 10.1006/jabr.1994.1302
Mikhail Muzychuk, Ádám’s conjecture is true in the square-free case, J. Combin. Theory Ser. A 72 (1995), no. 1, 118–134. MR 1354970, DOI 10.1016/0097-3165(95)90031-4
Mikhail Muzychuk, On the isomorphism problem for cyclic combinatorial objects, Discrete Math. 197/198 (1999), 589–606. 16th British Combinatorial Conference (London, 1997). MR 1674890
Mikhail Muzychuk, Mikhail Klin, and Reinhard Pöschel, The isomorphism problem for circulant graphs via Schur ring theory, Codes and association schemes (Piscataway, NJ, 1999) DIMACS Ser. Discrete Math. Theoret. Comput. Sci., vol. 56, Amer. Math. Soc., Providence, RI, 2001, pp. 241–264. MR 1816402, DOI 10.1090/dimacs/056/19
Mikhail E. Muzychuk and Gottfried Tinhofer, Recognizing circulant graphs of prime order in polynomial time, Electron. J. Combin. 5 (1998), Research Paper 25, 28. MR 1618814, DOI 10.37236/1363
Mikhail E. Muzychuk and Gottfried Tinhofer, Recognizing circulant graphs in polynomial time: an application of association schemes, Electron. J. Combin. 8 (2001), no. 1, Research Paper 26, 32. MR 1855867, DOI 10.37236/1570
P. P. Pálfy, A polynomial bound for the orders of primitive solvable groups, J. Algebra 77 (1982), no. 1, 127–137. MR 665168, DOI 10.1016/0021-8693(82)90281-2
I. N. Ponomarenko, Polynomial time algorithms for recognizing and isomorphism testing of cyclic tournaments, Acta Appl. Math. 29 (1992), no. 1-2, 139–160. Interactions between algebra and combinatorics. MR 1192837, DOI 10.1007/BF00053383
I. Schur, Zür Theorie der einfach transitiven Permutationsgruppen, S.-B. Preuss. Akad. Wiss. Phys.-Math. Kl. 18/20 (1933), 598–623.
B. Yu. Weisfeiler and A. A. Leman, Reduction of a graph to a canonical form and an algebra which appears in the process, Nauchno-Tekhn. Inform. Sb. VINITI Ser. 2 1968, no. 9, 12–16. (Russian)
On construction and identification of graphs, Lecture Notes in Mathematics, Vol. 558, Springer-Verlag, Berlin-New York, 1976. With contributions by A. Lehman, G. M. Adelson-Velsky, V. Arlazarov, I. Faragev, A. Uskov, I. Zuev, M. Rosenfeld and B. Weisfeiler; Edited by Boris Weisfeiler. MR 0543783
Helmut Wielandt, Finite permutation groups, Academic Press, New York-London, 1964. Translated from the German by R. Bercov. MR 0183775
—, Permutation groups through invariant relations and invariant functions, Lecture Notes Dept. Math., Ohio State Univ., Columbus, Ohio, 1969.