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
DOI: https://doi.org/10.1090/S1061-0022-04-00833-7
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. G. Birkhoff, Lattice theory, Amer. Math. Soc. Colloq. Publ., vol. 25, Amer. Math. Soc., Providence, RI, 1967. MR 0227053 (37:2638)
  • 3. A. E. Brouwer, A. M. Cohen, and A. Neumaier, Distance-regular graphs, Ergeb. Math. Grenzgeb. (3), vol. 18, Springer-Verlag, Berlin-New York, 1989. MR 1002568 (90e:05001)
  • 4. J. D. Dixon and B. Mortimer, Permutation groups, Grad. Texts in Math., vol. 163, Springer-Verlag, New York, 1996. MR 1409812 (98m:20003)
  • 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 parameters of a cellular algebra, Zap. Nauchn. Sem. S.-Peterburg. Otdel. Mat. Inst. Steklov. (POMI) 240 (1997), 82-95; English transl., J. Math. Sci. 96 (1999), no. 5, 3496-3504. MR 1691640 (2000c:20017)
  • 7. -, Isomorphism of coloured graphs with slowly increasing multiplicity of Jordan blocks, Combinatorica 19 (1999), 321-333. MR 1723252 (2001h:05070)
  • 8. S. Evdokimov, M. Karpinski, and I. Ponomarenko, On a new high-dimensional Weisfeiler-Leman algorithm, J. Algebraic Combin. 10 (1999), 29-45. MR 1701282 (2001i:05110)
  • 9. S. Evdokimov and I. Ponomarenko, Separability number and schurity number of coherent configurations, Electron. J. Combin. 7 (2000), no. 1, Res. Paper 31. MR 1763969 (2001g:05108)
  • 10. -, On a family of Schur rings over a finite cyclic group, Algebra i Analiz 13 (2001), no. 3, 139-154; English transl., St. Petersburg Math. J. 13 (2002), no. 3, 441-452. MR 1850191 (2002i:16036)
  • 11. -, Characterization of cyclotomic schemes and normal Schur rings over a cyclic group, Algebra i Analiz 14 (2002), no. 2, 11-55; English transl., St. Petersburg Math. J. 14 (2003), no. 2, 189-221. MR 1925880 (2003h:20005)
  • 12. D. G. Higman, Coherent configurations. , Rend. Sem. Mat. Univ. Padova 44 (1970), 1-25. MR 0325420 (48:3767)
  • 13. K. H. Leung and S. H. Man, On Schur rings over cyclic groups. , J. Algebra 183 (1996), 273-285. MR 1399027 (98h:20009)
  • 14. C. H. Li, On isomorphisms of finite Cayley graphs--a survey, Discrete Math. 256 (2002), 301-334. MR 1927074 (2003i:05067)
  • 15. A. Lubiw, Some NP-complete problems similar to graph isomorphism, SIAM J. Comput. 10 (1981), 11-21. MR 0605600 (82f:03036)
  • 16. E. 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 (94h:20005)
  • 17. M. E. Muzychuk, On the structure of basic sets of Schur rings over cyclic groups, J. Algebra 169 (1994), 655-678. MR 1297167 (95i:20004)
  • 18. -, Ádám's conjecture is true in the square-free case, J. Combin. Theory Ser. A 72 (1995), 118-134. MR 1354970 (96m:05141)
  • 19. -, On the isomorphism problem for cyclic combinatorial objects, Discrete Math. 197/198 (1999), 589-606. MR 1674890 (2000e:05165)
  • 20. M. Muzychuk, M. Klin, and R. 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 (2002g:05128)
  • 21. M. E. Muzychuk and G. Tinhofer, Recognizing circulant graphs of prime order in polynomial time, Electron. J. Combin. 5 (1998), no. 1, Res. Paper 25. MR 1618814 (99c:05186)
  • 22. -, Recognizing circulant graphs in polynomial time: an application of association schemes, Electron. J. Combin. 8 (2001), no. 1, Res. Paper 26. MR 1855867 (2002j:05141)
  • 23. P. P. Palfy, A polynomial bound for the orders of primitive solvable groups, J. Algebra 77 (1982), 127-137. MR 665168 (84c:20007)
  • 24. I. Ponomarenko, Polynomial-time algorithms for recognizing and isomorphism testing of cyclic tournaments, Acta Appl. Math. 29 (1992), 139-160. MR 1192837 (94f:05142)
  • 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. B. Weisfeiler (ed.), On the construction and identification of graphs, Lecture Notes in Math., vol. 558, Springer-Verlag, Berlin etc., 1976. MR 0543783 (58:27590)
  • 28. H. Wielandt, Finite permutation groups, Acad. Press, New York-London, 1964. MR 0183775 (32:1252)
  • 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
Email: evdokim@pdmi.ras.ru

I. N. Ponomarenko
Affiliation: St. Petersburg Branch, Steklov Mathematical Institute, Russian Academy of Sciences, Fontanka 27, St. Petersburg 191023, Russia
Email: inp@pdmi.ras.ru

DOI: https://doi.org/10.1090/S1061-0022-04-00833-7
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

American Mathematical Society