tailieunhanh - Báo cáo toán học: "Recognizing circulant graphs of prime order in polynomial time"

Tuyển tập các báo cáo nghiên cứu khoa học hay nhất của tạp chí toán học quốc tế đề tài: Recognizing circulant graphs of prime order in polynomial time. | Recognizing circulant graphs of prime order in polynomial time Mikhail E. Muzychuk Netanya Academic College 42365 Netanya Israel mikhail@ Gottfried Tinhofer Technical University of Munich 80290 Munchen Germany gottin@ Submitted December 19 1997 Accepted April 1 1998 Abstract A circulant graph G of order n is a Cayley graph over the cyclic group Zn. Equivalently G is circulant iff its vertices can be ordered such that the corresponding adjacency matrix becomes a circulant matrix. To each circulant graph we may associate a coherent configuration A and in particular a Schur ring S isomorphic to A. A can be associated without knowing G to be circu-lant. If n is prime then by investigating the structure of A either we are able to find an appropriate ordering of the vertices proving that G is circulant or we are able to prove that a certain necessary condition for G being circulant is violated. The algorithm we propose in this paper is a recognition algorithm for cyclic association schemes. It runs in time polynomial in n. MR Subject Number 05C25 05C85 05E30 Keywords Circulant graph cyclic association scheme recognition algorithm The work reported in this paper has been partially supported by the German Israel Foundation for Scientific Research and Development under contract 93 THE ELECTRONIC .JOURNAL OF COmBINATORICS 3 1996 RxX 2 1 Introduction The graphs considered in this paper are of the form X Y where X is a hnite set and Y is a binary relation on X which is not necessarily symmetric. Let G be a group and G X Y a graph with vertex set X G and with adjacency relation Y dehned with the aid of some subset C c G by Y g h g h 2 G A gh 1 2 C . Then G is called Cayley graph over the group G. Let Zn n 2 N stand for a cyclic group of order n written additively. A circulant graph G over Zn is a Cayley graph over this group. In this particular case the adjacency relation Y has the form n 1 Y u i x i Y 0 i 0 where Y 0 is .