Remote Access St. Petersburg Mathematical Journal

St. Petersburg Mathematical Journal

ISSN 1547-7371(online) ISSN 1061-0022(print)



Circulant graphs: recognizing and isomorphism testing in polynomial time

Authors: S. A. Evdokimov and I. N. Ponomarenko
Translated by: the authors
Original publication: Algebra i Analiz, tom 15 (2003), nomer 6.
Journal: St. Petersburg Math. J. 15 (2004), 813-835
MSC (2000): Primary 5C25, 20F65
Published electronically: November 16, 2004
MathSciNet review: 2044629
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • 1. 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.
  • 2. Garrett Birkhoff, Lattice theory, Third edition. American Mathematical Society Colloquium Publications, Vol. XXV, American Mathematical Society, Providence, R.I., 1967. MR 0227053
  • 3. 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
  • 4. John D. Dixon and Brian Mortimer, Permutation groups, Graduate Texts in Mathematics, vol. 163, Springer-Verlag, New York, 1996. MR 1409812
  • 5. S. Evdokimov, M. E. Muzychuk, I. Ponomarenko, and G. Tinhofer, Recognizing certain Cayley graphs in polynomial time (submitted to Electron. J. Combin.).
  • 6. 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, 10.1007/BF02175828
  • 7. 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, 10.1007/s004930050059
  • 8. 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, 10.1023/A:1018672019177
  • 9. Sergei Evdokimov and Ilia Ponomarenko, Separability number and Schurity number of coherent configurations, Electron. J. Combin. 7 (2000), Research Paper 31, 33. MR 1763969
  • 10. 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
  • 11. 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
  • 12. D. G. Higman, Coherent configurations. I, Rend. Sem. Mat. Univ. Padova 44 (1970), 1–25. MR 0325420
  • 13. Ka Hin Leung and Shing Hing Man, On Schur rings over cyclic groups. II, J. Algebra 183 (1996), no. 2, 273–285. MR 1399027, 10.1006/jabr.1996.0220
  • 14. Cai Heng Li, On isomorphisms of finite Cayley graphs—a survey, Discrete Math. 256 (2002), no. 1-2, 301–334. MR 1927074, 10.1016/S0012-365X(01)00438-1
  • 15. Anna Lubiw, Some NP-complete problems similar to graph isomorphism, SIAM J. Comput. 10 (1981), no. 1, 11–21. MR 605600, 10.1137/0210002
  • 16. 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, 10.1016/S0166-4115(08)62656-4
  • 17. 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, 10.1006/jabr.1994.1302
  • 18. 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, 10.1016/0097-3165(95)90031-4
  • 19. 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
  • 20. 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
  • 21. Mikhail E. Muzychuk and Gottfried Tinhofer, Recognizing circulant graphs of prime order in polynomial time, Electron. J. Combin. 5 (1998), Research Paper 25, 28 pp. (electronic). MR 1618814
  • 22. 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 pp. (electronic). MR 1855867
  • 23. P. P. Pálfy, A polynomial bound for the orders of primitive solvable groups, J. Algebra 77 (1982), no. 1, 127–137. MR 665168, 10.1016/0021-8693(82)90281-2
  • 24. 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, 10.1007/BF00053383
  • 25. I. Schur, Zür Theorie der einfach transitiven Permutationsgruppen, S.-B. Preuss. Akad. Wiss. Phys.-Math. Kl. 18/20 (1933), 598-623.
  • 26. 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)
  • 27. Boris Weisfeiler (ed.), 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. MR 0543783
  • 28. Helmut Wielandt, Finite permutation groups, Translated from the German by R. Bercov, Academic Press, New York-London, 1964. MR 0183775
  • 29. -, Permutation groups through invariant relations and invariant functions, Lecture Notes Dept. Math., Ohio State Univ., Columbus, Ohio, 1969.

Similar Articles

Retrieve articles in St. Petersburg Mathematical Journal with MSC (2000): 5C25, 20F65

Retrieve articles in all journals with MSC (2000): 5C25, 20F65

Additional Information

S. A. Evdokimov
Affiliation: St. Petersburg Institute for Informatics and Automation RAS, St. Petersburg, Russia

I. N. Ponomarenko
Affiliation: St. Petersburg Branch, Steklov Mathematical Institute, Russian Academy of Sciences, Fontanka 27, St. Petersburg 191023, Russia

Keywords: Regular cycle automorphism group, Cayley graph, polynomial-time algorithm
Received by editor(s): May 15, 2003
Published electronically: November 16, 2004
Additional Notes: Supported by RFBR (grants nos. 01-01-00219 and 03-01-00349). The second author was supported by RFBR, grants nos. 02-01-00093 and NSh-2251.2003.1.
Article copyright: © Copyright 2004 American Mathematical Society