Recognizing circulant graphs of prime order in polynomial time ^{∗}

Mikhail E. Muzychuk Netanya Academic College 42365 Netanya, Israel

mikhail@netvision.net.il

Gottfried Tinhofer Technical University of Munich 80290 München, Germany

gottin@mathematik.tu-muenchen.de

Submitted: December 19, 1997; Accepted: April 1, 1998

Abstract

A circulant graph G of order n is a Cayley graph over the cyclic group Z_{n}. 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 circulant. 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 # I-0333-263.06/93

1 Introduction

The graphs considered in this paper are of the form (X, γ), where X is a finite set and γ is a binary relation on X which is not necessarily symmetric.

Let G be a group and G = (X, γ) a graph with vertex set X = G and with adjacency relation γ defined with the aid of some subset C ⊂ G by

γ = {(g, h) : g, h ∈ G ∧ gh^{−1} ∈ C}.

Then G is called Cayley graph over the group G.

Let Z_{n}, n ∈ N, stand for a cyclic group of order n written additively. A circulant graph G over Z_{n} is a Cayley graph over this group. In this particular case, the adjacency relation γ has the form

γ = ⋃_{i=0}^{n−1}{i} × {i + γ(0)}

where γ(0) is the set of successors of the vertex 0. Evidently, the set of successors γ(i) of an arbitrary vertex i satisfies γ(i) = i + γ(0).

The set γ(0) is called the connection set of the circulant graph G. G is a simple undirected graph if 0 ∉ γ(0) and j ∈ γ(0) implies −j ∈ γ(0).

There are different equivalent characterizations of circulant graphs. One of them is this: A graph G is a circulant graph iff its vertex set can be numbered in such a way that the resulting adjacency matrix A(G) is a circulant matrix. We call such a numbering a Cayley numbering. Still another characterization is: G is a circulant graph iff a cyclic permutation of its vertices exists which is an automorphism of G.

Cayley graphs, and in particular, circulant graphs have been studied intensively in the literature. These graphs are easily seen to be vertex transitive. In the case of a prime vertex number n circulant graphs are known to be the only vertex transitive graphs. Because of their high symmetry, Cayley graphs are ideal models for communication networks. Routing and weight balancing is easily done on such graphs.

Assume that a graph G on the set V (G) = {0, …, n − 1} is given by its diagram or by its adjacency matrix, or by some other data structure commonly used in dealing with graphs. How can we decide whether G is a Cayley graph or not? In such a generality, this decision problem seems to be far from beeing tractable efficiently. A recognition algorithm for Cayley graphs would have to involve implicitly checking all finite groups of order n. In the special case of circulant graphs, or in any other case where the group G is given, we could recognize Cayley graphs by checking all different numberings of the vertex set and comparing the corresponding adjacency matrix with the group table of G. This ad hoc procedure is of course not efficient.

To our knowledge the first result towards recognizing circulant graphs can be found in [Pon92] where circulant tournaments have been considered. In the present paper we shall settle the case of a prime number n of vertices, i.e. we shall propose a still somewhat complicated, but nevertheless time-polynomial, method for recognizing arbitrary circulant graphs of prime order. Our method is based on the notions of coherent configurations ([Hig70]), the Bose-Mesner algebra of which is a coherent algebra ([Hig87]) (also called cellular algebra, [Wei76]), and Schur rings generated by G and on the interrelations between these notions when G possesses a cyclic automorphism. Since the coherent configuration generated by G has the same automorphism group as G, our method can be introduced as a method for recognizing coherent configurations having a full cyclic automorphism. The properties of coherent configurations and Schur rings we have to use in the construction of the recognition algorithm are presented basically in earlier papers of the first author or can be found in the literature. They have been exploited in joint work with the second author for the purpose of this paper.

In order to make this paper self-contained and readable not only for insiders in the theory of coherent configurations we start with a small collection of the basic notions in this theory. This is done in Section 2. In Section 3 we relate cyclic configurations to the corresponding Schur rings and list up the basic facts of these algebraic structures which are used in the remaining sections. In Section 4 the recognition algorithm for cyclic configurations of prime order is discussed. In Section 5 we give a more formal description of our algorithm and a rough estimation of its time complexity. We end up with some examples in order to demonstrate how our algorithm works.

2 Coherent configurations.

Let X be a finite set. We use small Greek letters for binary relations on X and capital Greek letters for sets of such relations. A set Γ of binary relations on X is called a coherent configuration [Hig87] if it satisfies the following axioms:

• (CC1) There exists a subset Π ⊂ Γ such that the identical relation ε_{X} = {(x, x) | x ∈ X} is a union of π ∈ Π, ε_{X} = ⋃_{π∈Π} π.

• (CC2) The relations from Γ form a partition of X^{2};

• (CC3) ∀γ ∈ Γ, γ^{t} = {(x, y) | (y, x) ∈ γ} ∈ Γ;

• (CC4) For each triple α, β, γ ∈ Γ and a pair (x, y) ∈ γ the number

p_{α,β}^{γ} = |{z ∈ X | (x, z) ∈ α, (z, y) ∈ β}|

does not depend on the choice of the pair (x, y) ∈ γ.

The elements of Γ are called basic relations and their graphs are called basic graphs of (X; Γ).

For arbitrary two relations γ, ρ ∈ Γ we define the product γρ by

γρ = {(x, y) | ∃z : (x, z) ∈ γ ∧ (z, y) ∈ ρ}.

We shall write γ^{2} for γγ.

For any relation γ ∈ Γ and a point x ∈ X we set

γ(x) = {y ∈ X | (x, y) ∈ γ}.

For Π ⊂ Γ, let Π(x) = ⋃_{π∈Π} π(x).

A coherent configuration (X; Γ) is called homogeneous if

• (CC5) ∀_{γ∈Γ}∀_{x,y∈X}(|γ(x)| = |γ(y)|).

In the case of (X; Γ) being homogeneous we write Γ^{∗} for Γ \ {ε_{X}}.

An adjacency matrix A(γ), γ ∈ Γ, is an X × X matrix whose (x, y)-entry is 1 if (x, y) ∈ γ and 0 otherwise. Suppose that Γ = {γ_{0}, γ_{1}, …, γ_{t}} with γ_{0} = ε_{X}. The matrix

Adj((X; Γ)) = ∑_{i=0}^{t} i · A(γ_{i})

is called the adjacency matrix of (X; Γ).

The complex vector subspace of M_{X}(C) spanned by the adjacency matrices A(γ), γ ∈ Γ, is a complex matrix algebra of dimension |Γ| which is known as the Bose-Mesner algebra of (X; Γ). The automorphism group Aut(X; Γ) is a subgroup of the symmetric group Sym(X) defined as follows

Aut(X; Γ) = {g ∈ Sym(X) | ∀_{γ∈Γ}(γ^{g} = γ) }.

We set Rel(Γ) = {⋃_{γ∈Π} γ | Π ⊂ Γ}. In other words, Rel(Γ) is the set of all binary relations that may be obtained as unions of those belonging to Γ. We say that a coherent configuration (X; Π) is a fusion of a coherent configuration (X; Γ) (and (X; Γ) is called a fission of (X; Π)) if Rel(Π) ⊂ Rel(Γ) (see [BaI84]). The relation Rel(Π) ⊂ Rel(Γ) is a partial ordering on the set of all coherent configurations defined on X.

An equivalence relation τ ⊂ X^{2} is said to be non-trivial if the number of equivalence classes is strictly greater than 1 and less than |X|. A homogeneous coherent configuration (X; Γ) is called imprimitive if Rel(Γ) contains a non-trivial equivalence relation. If Rel(Γ) does not contain such a relation, then (X; Γ) is said to be primitive.

If Φ is any set of binary relations defined on X, then by (X; ⟨Φ⟩) we denote the minimal coherent configuration (X; Γ) satisfying the property: Φ ∈ Rel(Γ). Such a configuration is unique and may be found by the Weisfeiler-Leman algorithm in time O(|X|^{3} log(|X|)) (see [BBLT97]). A version of this algorithm with much higher timecomplexity, but nevertheless very efficient in the range up to n = 1000, is presented in [BCKP97].

For any Y ⊂ X and γ ∈ Γ we define Γ_{Y} = {γ ∩ (Y × Y) | γ ∈ Γ}. Given a point x ∈ X and γ ∈ Γ, one can consider the coherent configuration (γ(x); ⟨Γ_{γ(x)}⟩). In what follows we shall denote this configuration as (γ(x); Γ^{γ(x)}).

We say that a coherent configuration (X; Γ) is cyclic if its automorphism group contains a full cycle, i.e., a permutation of the form g = (x_{1}, ..., x_{n}), where n = |X|. The cyclic group C_{n} generated by g acts transitively on X. Therefore, Aut(X; Γ) is a transitive permutation group and (X; Γ) is homogeneous.

Note that a graph G = (X, γ) is a circulant graph iff the coherent configuration (X; ⟨{γ}⟩) is cyclic. Therefore, the main question considered in this paper can be reformulated in the following way:

Find an algorithm with time-complexity polynomial in |X| that answers the question: Is a given homogenous coherent configuration cyclic?

To create such an algorithm one has first to study the properties of cyclic coherent configurations.

3 Properties of cyclic coherent configurations.

Let (X; Γ) be a cyclic coherent configuration and g ∈ Aut(X; Γ) be a full cycle. Fix an arbitrary point x ∈ X and consider the mapping

log_{g,x} : Γ → 2^{Z_{n}}

defined as follows:

log_{g,x}(γ) = {k ∈ Z_{n} | (x, x^{g^{k}}) ∈ γ}.

Proposition 3.1 The mapping log_{g,x} does not depend on the choice of the point x ∈ X.

Proof. Take an arbitrary relation γ ∈ Γ and two points x, y ∈ X. Clearly, y = x^{g^{l}} for a suitable l ∈ Z_{n}. By definition

k ∈ log_{g,x}(γ) ⇔ (x, x^{g^{k}}) ∈ γ

Since g ∈ Aut(X; Γ),

(x, x^{g^{k}}) ∈ γ ⇔ (x^{g^{l}}, x^{g^{k+l}}) ∈ γ ⇔ (y, y^{g^{k}}) ∈ γ ⇔ k ∈ log_{g,y}(γ)

finishing the proof. ♢

Thus we shall write log_{g}(γ) instead of log_{g,x}(γ). An easy check shows that log_{g}(ε_{X}) = {0}, where ε_{X} is the identical relation on X.

It should be mentioned that in general log_{g}(γ) depends on the choice of the full cycle g ∈ Aut(X; Γ).

Given a subset T ⊂ Z_{n}, we define a binary relation exp_{g}(T) as follows:

exp_{g}(T) = {(z, z^{g^{k}}) | k ∈ T, z ∈ X}.

The following proposition is easy to check.

Proposition 3.2 (i) exp_{g}(log_{g}(γ)) = γ, log_{g}(exp_{g}(T)) = T;

(ii) Let γ ≠ σ ∈ Γ be two arbitrary relations. Then log_{g}(γ) ∩ log_{g}(σ) = ∅;

(iii) For arbitrary γ ∈ Γ we have log_{g}(γ^{t}) = −log_{g}(γ);

(iv) If A(γ), γ ∈ Γ, is the adjacency matrix of γ ∈ Γ and P_{g} is the permutation matrix of g, then A(γ) = ∑_{k∈log_{g}(γ)} P_{g}^{k};

(v) ⋃_{γ∈Γ} log_{g}(γ) = Z_{n};

(vi) γ ∈ Rel(Γ) is an equivalence relation if and only if log_{g}(γ) is a subgroup of Z_{n}.

The mapping log_{g} assigns to a cyclic coherent configuration a certain partition of Z_{n}. To characterize all partitions obtainable in this way from coherent configurations we need the notion of a Schur ring.

3.1 Schur rings.

Let H be a finite group written multiplicatively and with identity e. Let ZH be the group algebra over the ring Z of integers. Given any subset T ⊂ H, we denote by \underline{T} the following element of ZH: \underline{T} = ∑_{t∈T} t. According to [Wie64] we call such elements simple quantities.

Definition.[Wie64] A Z-subalgebra S ⊂ ZH is called Schur ring (briefly S-ring) over H if it satisfies the following conditions:

• (S1) There exists a basis of S consisting of simple quantities \underline{T}_{0}, \underline{T}_{1}, ..., \underline{T}_{r}; • (S2) T_{0} = {e} and ∪_{i=0}^{r}T_{i} = H;

• (S3) T_{i} ∩ T_{j} = ∅ if i ≠ j;

• (S4) For each i ∈ {0, 1, ..., r} there exists i′ ∈ {0, 1, ..., r} such that T_{i′} = {t^{−1}|t ∈ T_{i}}.

The basis \underline{T}_{0}, ..., \underline{T}_{r} is called the standard basis and the simple quantities \underline{T}_{i} (resp. the sets T_{i}) are called basic quantities (resp. basic sets) of S. The notation S = ⟨\underline{T}_{0}, ..., \underline{T}_{r}⟩ means that \underline{T}_{0}, ..., \underline{T}_{r} is the standard basis of S. We say that a subset R ⊂ Z_{n} belongs to an S-ring S if \underline{R} ∈ S. It is clear that an S-ring S is closed under all set-theoretical operations over the subsets belonging to S. An S-ring S′ over the group H is an S-subring of an S-ring S defined over the same group H if S′ ⊂ S.

The connection between Schur rings and cyclic coherent configurations is given by the following statement.

Lemma 3.3 Let g ∈ Sym(X) be an arbitrary full cycle and (X; Γ) be a g-invariant coherent configuration. Then the map Γ ↦ log_{g}(Γ) is a bijection between g-invariant coherent configurations and Schur rings over Z_{n}. Moreover, the map A(γ) ↦ \underline{log_{g}(γ)} defines an isomorphism between the Bose-Mesner algebra of (X; Γ) and the Schur ring ⟨\underline{log_{g}(γ)}⟩_{γ∈Γ}.

Proof. It follows from Proposition 3.2 that the sets log_{g}(γ) form a partition of Z_{n}. Thus we have to check that the Z-module sp\{\underline{log_{g}(γ)}\}_{γ∈Γ} is closed with respect to the group algebra multiplication.

Let α, β, γ ∈ Γ be an arbitrary triple of basic relations. Take an arbitrary k ∈ log_{g}(γ). To each pair u ∈ log_{g}(α), v ∈ log_{g}(β) that satisfies u+v = k one can associate a triple of points x, x^{g^{u}}, x^{g^{k}}. Clearly (x, x^{g^{u}}) ∈ α, (x^{g^{u}}, x^{g^{k}}) ∈ β and (x, x^{g^{k}}) ∈ γ. Thus the number of solutions of the equation u+v = k where u ∈ log_{g}(α), v ∈ log_{g}(β) does not depend on the choice of k ∈ log_{g}(γ) and is equal to p_{α,β}^{γ}. Therefore, sp\{\underline{log_{g}(γ)}\}_{γ∈Γ} is closed with respect to the group algebra multiplication and its structure constants coincide with those of the Bose-Mesner algebra of Γ. Hence

A(γ) ↦ \underline{log_{g}(γ)}

induces an isomorphism between the algebras. ♢

As a first consequence of this claim we obtain the following property of cyclic coherent configurations.

Proposition 3.4 If (X; Γ) is a cyclic coherent configuration, then its Bose-Mesner algebra is commutative.

A coherent configuration the Bose-Mesner algebra of which is commutative is known as association scheme [BaI84]. For this reason we shall call a cyclic coherent configuration a cyclic association scheme.

Proposition 3.5 Let (X; Γ) be a non-trivial cyclic association scheme and let g ∈ Aut(Γ) be a full cycle. Then the following statements hold:

(i) (X; Γ) is primitive iff |X| is prime.

(ii) Assume that (X; Γ) is imprimitive and let π ∈ Rel(Γ) be a non-trivial equivalence relation. Then each equivalence class π(x), x ∈ X is an orbit of a subgroup ⟨g^{n/d}⟩ where d = |π(x)|.

(iii) If (X; Γ) is an imprimitive cyclic scheme, then it has a unique non-trivial equivalence relation τ ∈ Rel(Γ) with a maximal number of classes.

Proof. (i) follows from Theorem 25.3 of [Wie64]. (ii) π is an equivalence relation invariant under Aut(X; Γ). Therefore, π is invariant under the action of C_{n} = ⟨g⟩ which acts regularly on X. Now the claim becomes evident. Part (iii) is a direct consequence of the previous part. ♢

3.2 Cyclic association schemes of prime degree.

In this subsection we assume that |X| = p, where p is a prime. The structure of all cyclic schemes of prime degree is well-known since 1978 (see [KliP78]). To describe it we identify X with a finite field F_{p}. We also assume that the full cycle g = (0, 1, ..., p − 1) is an automorphism of our scheme. Clearly, x^{g} = x + 1, x ∈ F_{p}.

Fix an arbitrary subgroup M ≤ F_{p}^{∗}, |M| = d. Then F_{p}^{∗} is a union of M-cosets:

F_{p}^{∗} = Mt_{1} ∪ ... ∪ Mt_{r}, t_{1} = 1, r = (p − 1)/d.

For each Mt_{i} we set γ_{i} = {(x, y) | x − y ∈ Mt_{i}}.

Theorem 3.1

(i) The set Γ_{M} = {ε_{X}, γ_{1}, ..., γ_{r}} of binary relations forms a cyclic association scheme on F_{p}, g ∈ Aut(F_{p}; Γ_{M}).

(ii) Aut(F_{p}; Γ_{M}) = Aff(M, F_{p}), where Aff(M, F_{p}) is the group of all permutations of the form f(x) = mx + a, m ∈ M, a ∈ F_{p}.

(iii) Every cyclic association scheme (F_{p}; Γ) with g ∈ Aut(F_{p}; Γ) coincides with (F_{p}; Γ_{M}) for a suitable M ≤ F_{p}^{∗}.

(iv) The graphs (F_{p}, γ_{i}), i = 1, ..., r are pairwise isomorphic.

(v) The graph (F_{p}, γ_{1}) is symmetric if and only if |M| is even.

(vi) (F_{p}; Γ_{M}) is a fusion scheme of (F_{p}; Γ_{M′}) if and only if M′ ≤ M.

Proof.

(i) Γ_{M} is the set of 2-orbits (= orbitals) of Aff(M, F_{p}). (ii) See [McC63], [FarIK92]. (iii) This follows from the classifications of S-rings over F_{p}, see [FarIK92]. (iv) - (vi) These statements are trivial conclusions from (i) - (iii). ♢

The claim below contains the main properties of the association schemes (F_{p}; Γ_{M}), M ≤ F_{p}^{∗}.

Lemma 3.6 Assume M ≤ F_{p}^{∗}, 1 < |M| < p − 1. For any x ∈ F_{p} and γ ∈ Γ_{M}^{∗}

(i) all coherent configurations (γ(x); (Γ_{M})^{γ(x)}) are pairwise isomorphic and

(ii) if |M| > 2, then (γ(x); (Γ_{M})^{γ(x)}) is a non-trivial cyclic association scheme.

Proof.

(i) Since Aut(F_{p}; Γ_{M}) is transitive, (γ(x); (Γ_{M})^{γ(x)}) and (γ(y); (Γ_{M})^{γ(y)}) are isomorphic for any pair x, y ∈ F_{p}. Thus we have to show that

(γ_{1}(0); (Γ_{M})^{γ_{1}(0)}) ≅ (γ_{i}(0); (Γ_{M})^{γ_{i}(0)})

for each i = 1, ..., r. Take the permutation x → xt_{i}. A direct check shows that γ_{1}^{t_{i}} = γ_{i} and ∀_{γ_{j}∈Γ}(γ_{j}^{t_{i}} ∈ Γ). Therefore, (γ_{1}(0); (Γ_{M})^{γ_{1}(0)})^{t_{i}} = (γ_{i}(0); (Γ_{M})^{γ_{i}(0)}), as desired.

(ii) It is enough to prove this part only for γ = γ_{1} and x = 0. In this case γ_{1}(0) = M and (γ_{1}(0); (Γ_{M})^{γ_{1}(0)}) = (M; (Γ_{M})^{M}). Let us write Γ_{M}^{0} instead of (Γ_{M})^{M}.

The point stabilizer (Aut(F_{p}; Γ_{M}))_{0} is a subgroup of Aut(M; Γ_{M}^{0}). It consists of all permutations of the form x → mx, m ∈ M. Since (Aut(F_{p}; Γ_{M}))_{0} acts regularly on M, Aut(M; Γ_{M}^{0}) contains a regular subgroup isomorphic to M. Since M is cyclic, (M; Γ_{M}^{0}) is a cyclic association scheme.

To finish the proof we have to show that (M; Γ_{M}^{0}) is non-trivial. Assume the contrary, i.e., assume that (M; Γ_{M}^{0}) has only two basic relations: ε_{M} and M^{2} \ε_{M}. Take γ_{i} ∈ Γ^{∗} such that γ_{i} ∩ M^{2} \ ε_{M} ≠ ∅. Then, γ_{i} ∩ M^{2} = M^{2} \ ε_{M}.

Take an arbitrary point m ∈ M = γ_{1}(0). Then (0, m) ∈ γ_{1}. For each m′ ∈ γ_{1}(0) such that m′ ≠ m we have that (0, m′) ∈ γ_{1} and (m′, m) ∈ γ_{i}. Therefore,

p_{γ_{1},γ_{i}}^{γ_{1}} = |M| − 1.

Since γ_{i} is of degree |M|, for each m ∈ M there is a z_{m} ∉ M such that γ_{i}(m) = M \{m}∪{z_{m}}. Fix m ∈ M. From p_{γ_{1},γ_{i}}^{γ_{1}} = |M|−1 it follows that for every a ∈ γ_{1}^{t}(m) there is a y_{a} ∈ M \ {m} such that γ_{1}(a) = M \ {y_{a}} ∪ {z_{m}}. Moreover, y_{a} ≠ y_{a′} for a ≠ a′ (for otherwise F_{p} would have a non-trivial subgroup). This implies that every two elements m, m′ ∈ M have exactly |M| − 1 joint predecessors with respect to γ_{1}. From this it follows

p_{γ_{1}^{t},γ_{1}}^{γ_{i}} = |M| − 1,

and

A(γ_{1}^{t})A(γ_{1}) = |M|I_{X} + (|M| − 1)A(γ_{i}) (1)

where I_{X} is the unit matrix. Now the proof is completed by applying Theorem 2.3.10(i) from [FarKM94]. According to this theorem we have

|M| − 1 ≤ \frac{|M|}{2}

which is true only for |M| ≤ 2, a contradiction to our hypothesis.

4 How to recognize cyclic coherent configurations.

Let (X; Γ) be a homogeneous coherent configuration with |X| = p, p a prime. We shall present a method for finding a full cyclic automorphism of (X; Γ), provided this configuration is cyclic.

We set r := |Γ| − 1. If some relations have different valencies, then (X; Γ) is not cyclic. Thus we may assume that |γ(x)| = d, d = (p − 1)/r for all γ ∈ Γ. The case d = 1 is trivial. In this case each basic graph (X, γ_{i}) is a full cycle which defines a full cyclic automorphism. Hence, assume 1 < d < p−1. There are two possible cases: d is composite and d is prime.

4.1 Case of d being composite.

If (X; Γ) is a cyclic scheme corresponding to a subgroup M ≤ F_{p}^{∗}, then it is a fusion of a cyclic scheme (X; Γ′) corresponding to some proper subgroup M′ ≤ M, 1 < |M′| < |M| which exists, since |M| is not prime.

The main idea is to build the fission (see [BaS93]) scheme (X; Γ′) by purely combinatorial methods and to apply the algorithm to a new scheme.

Step 1. For each point x ∈ X and each γ ∈ Γ^{∗} we compute, using the WL-algorithm, (γ(x); Γ^{γ(x)}). If (γ(x); Γ^{γ(x)}) is not homogeneous, then the initial scheme is not cyclic. Thus we may assume that (γ(x); Γ^{γ(x)}) is homogeneous for all x ∈ X.

If (X; Γ) is cyclic, then, by Lemma 3.6, (γ(x); Γ^{γ(x)}) is a non-trivial cyclic scheme. Since |M| is composite, (γ(x); Γ^{γ(x)}) is imprimitive and, therefore, there exists a unique equivalence relation τ_{x,γ} ∈ Rel(Γ^{γ(x)}) with a maximal number of classes (Proposition 3.5(ii)). The schemes (γ(x); Γ^{γ(x)}), x ∈ X, γ ∈ Γ^{∗} should be pairwise isomorphic. Therefore, the number of classes of τ_{x,γ} should not depend on the choice of x ∈ X, γ ∈ Γ^{∗}.

Step 2. For each x ∈ X and γ ∈ Γ^{∗} we find a nontrivial equivalence relation τ_{x,γ} ∈ Rel(Γ^{γ(x)}) with a maximal number of classes. If for some pair x, γ the scheme (γ(x); Γ^{γ(x)}) has more than one such equivalence relation, then the initial scheme is not cyclic. If there are two pairs (x, γ) ≠ (x′, γ′) such that τ_{x,γ} and τ_{x′,γ′} have different number of classes, then (X; Γ) is not cyclic. So we may assume that τ_{x,γ} always has s classes of cardinality d′, sd′ = d. Since τ_{x,γ} should be non-trivial, 1 < d′ < d.

Every τ_{x,γ} is an equivalence relation on γ(x). For each x ∈ X we define an equivalence relation of X by setting

τ_{x} = ⋃_{γ∈Γ^{∗}} τ_{x,γ} ∪ {(x, x)}. (2)

It follows from the definition that each equivalence class of τ_{x} distinct from {x} contains exactly d′ elements.

Proposition 4.1 Assume (X; Γ) ≅ (F_{p}; Γ_{M}), |M| = d. Let M′ < M be the unique subgroup of order d′. Then for each x ∈ F_{p} the equivalence relation τ_{x} has the following form:

τ_{x} = ⋃_{γ′∈Γ_{M′}}(γ′(x) × γ′(x)).

Proof. Since Aut(F_{p}; Γ_{M}) is transitive, we may assume x = 0. Let (y, z) ∈ τ_{0} be an arbitrary pair. Since the case y = z = 0 is trivial, we may assume that y ≠ 0 ≠ z. By definition of τ_{x}, there exists γ ∈ Γ_{M} such that y, z ∈ γ(0) and (y, z) ∈ τ_{0,γ}. (Aut(X; Γ))_{0} is a cyclic subgroup of Aut(γ(0); Γ^{γ(0)}) of order d. Its generator g is a product g_{1} · ... · g_{r} of r = (p − 1)/d disjoint cycles of the same length d. Thus γ(0) is an orbit of a suitable group ⟨g_{i}⟩. WLOG we may assume that γ(0) is an orbit of ⟨g_{1}⟩. Thus g_{1} is a full cyclic automorphism of (γ(0); Γ^{γ(0)}). According to Proposition 3.5(ii) each equivalence class of τ_{0,γ} is an orbit of ⟨g_{1}^{d/d′}⟩. Hence the equivalence classes of τ_{0,γ} are the orbits of ⟨g_{1}^{d/d′}⟩, and, therefore, they are orbits of ⟨g^{d/d′}⟩. Thus, each equivalence class of τ_{0} is an orbit of ⟨g^{d/d′}⟩. Since g^{d/d′} is of order d′, it generates M′. But the orbits of M′ on F_{p} are exactly the sets γ′(0), γ′ ∈ Γ_{M′}. ♢

Our next step is to show that the set {τ_{x}}_{x∈X} defines the association scheme (F_{p}; Γ_{M′}) uniquely.

Lemma 4.2 Let (X; Ψ) be a primitive association scheme. Assume that all nontrivial valencies of Ψ are strictly greater than 1.^{1} For each x ∈ X we define an equivalence relation τ_{x} as follows

τ_{x} = ⋃_{γ∈Ψ^{∗}}(γ(x) × γ(x)).

Let Φ be a graph with node set X^{2} \ ε_{X} and with two nodes (x, y), (z, w) ∈ X^{2} \ ε_{X} connected by an edge iff either x = z ∧ (y, w) ∈ τ_{x} or y = w ∧ (x, z) ∈ τ_{y}. Then the set of connected components of Φ coincides with the set of relations Ψ^{∗}.

Proof. Let (x, y) and (z, w) be two nodes connected by an edge in Φ, If x = z, then y, w ∈ γ(x) for some γ ∈ Ψ^{∗}, or, equivalently, (x, y), (z, w) ∈ γ. If w = y, then x, z ∈ β(y) for some β ∈ Ψ^{∗} implying (x, y), (z, w) ∈ β^{t}. Thus, any two nodes (x, y), (z, w) connected by an edge in Φ lie at the same relation γ ∈ Ψ^{∗}. Therefore, each relation from Ψ^{∗} is a union of connected components of Φ.

Take now (x, y), (x′, y′) ∈ γ ∈ Ψ^{∗} and show that there exists a path in Φ starting in (x, y) and finishing at (x′, y′).

Since γ is non-trivial of valency greater than 1, γγ^{t} is a non-identical symmetric relation. Therefore γγ^{t} is connected and there exists a path x = x_{1}, ..., x_{m+1} = x′ with (x_{i}, x_{i+1}) ∈ γγ^{t}, i = 1, ..., m. Since (x_{i}, x_{i+1}) ∈ γγ^{t}, there exists z_{i} ∈ X such that (x_{i}, z_{i}) ∈ γ, (x_{i+1}, z_{i}) ∈ γ. But now we have the following path in Φ :

[figure: x = x_{1}; γ; y; γ; z_{1}; γ; x_{2}; γ; z_{2}; γ; x_{3}; …; x_{m}; γ; z_{m}; γ; x_{m+1} = x′; γ; y′]

♢

Step 3. For each x ∈ X we build an equivalence relation according to formula (2). After that we find connected components of the graph (X^{2} \ ε_{X}; Φ) defined in Lemma 4.2. If these components don’t form an association scheme on X, then (X; Γ) is not cyclic. Otherwise we obtain a new association scheme (X; Γ′). If there is a relation γ′ ∈ Γ′ whose valency is not equal to d′, then (X; Γ) is not cyclic.

Suppose that all non-trivial relations of Γ′ are of valency d′. If d′ is composite, then we go to Step 1. If d′ is prime, then we apply another method which is described in the next subsection.

4.2 Case of d being prime.

If d = 2, then the graph of every γ ∈ Γ^{∗} should be a non-oriented p-cycle. So, if some of these graphs has not this property, then the scheme is not cyclic. If all the basic graphs are non-oriented cycles, then by orienting one of them we obtain the automorphism we searched for. Thus we may assume that d is odd. In this case, by Theorem 3.1(v), γ ≠ γ^{t} for all γ ∈ Γ^{∗}.

1A primitive association scheme that contains a basic relation of valency 1 is isomorphic to the full cyclic scheme on a prime number of points.

Proposition 4.3 Let M ≤ F_{p}^{∗} be a subgroup of odd order. Then for each a ∈ F_{p} the mapping i_{a} defined by x^{i_{a}} = 2a − x, x ∈ F_{p} is the only involution from Sym(F_{p}) satisfying

(i) a^{i_{a}} = a;

(ii) ∀_{γ∈Γ}(γ^{i_{a}} = γ^{t});

Proof. By direct check we can see that i_{a} really satisfies (i) and (ii). Let now j ∈ S(F_{p}) be an involution that satisfies (i) and (ii). Then i_{a}j is an automorphism of (F_{p}; Γ_{M}). Therefore, i_{a}j ∈ Aff(M, F_{p}), implying j ∈ Aff(F_{p}^{∗}, F_{p}). That means there exist b, c ∈ F_{p}, b ≠ 0 such that x^{j} = bx + c, x ∈ F_{p}. Since j is an involution that fixes a, we find b = −1, c = 2a. ♢

The main idea of the algorithm is to reconstruct the involution i_{a}, a ∈ X by purely combinatorial methods. After that we multiply i_{a} with i_{b} for some b ≠ a. If the product is a full cycle that belongs to Aut(X; Γ), then we are done. Otherwise (X; Γ) is not a cyclic scheme.

Let now d be an odd prime and (X; Γ) be a homogeneous coherent configuration, with |γ(x)| = d for all γ ∈ Γ^{∗} and x ∈ X. Since the order and the valency of each γ ∈ Γ are odd, Γ does not contain symmetric relations. So γ ≠ γ^{t} for all γ ∈ Γ^{∗}. Fix an arbitrary point a ∈ X and set \overline{γ}(a) = γ(a) ∪ γ^{t}(a). For each β ∈ Γ^{∗} we define the binary relation β̂ ⊂ (\overline{γ}(a))^{2} as follows

β̂ = β ∩ (γ(a) × γ^{t}(a)).

By Φ(a, γ) we denote the following set of binary relations on \overline{γ}(a) :

Φ(a, γ) = \{ε_{\overline{γ}(a)}, (γ(a))^{2} ∪ (γ^{t}(a))^{2}\} ∪ \{β̂ ∪ (β̂)^{t}\}_{β∈Γ^{∗}}.

Proposition 4.4 If (X; Γ) ≅ (F_{p}; Γ_{M}), |M| = d, d is odd, then the coherent configuration (\overline{γ}(a); ⟨Φ(a, γ)⟩) is cyclic.

Proof. The stabilizer G_{a} := (Aut(F_{p}; Γ_{M}))_{a} consists of all permutations of the form x ↦ m(x − a) + a, m ∈ M, and, therefore is a cyclic group of odd order d. Since i_{a} centralizes G_{a}, the group ⟨G_{a}, i_{a}⟩ is cyclic of order 2d. Note that, if m̄ ∈ M is a generator of M, then the mapping x → −m̄(x − a) + a is a generator of ⟨G_{a}, i_{a}⟩. The orbits on F_{p} \ \{a\} of this group coincides with the sets \overline{γ}(a), γ ∈ Γ^{∗}.

We claim that every relation from Φ(a, γ) is invariant under the group ⟨G_{a}, i_{a}⟩. Indeed, the invariance under G_{a} follows immediately from the definition of the set Φ(a, γ).

Since \overline{γ}(a) is i_{a}-invariant, ε_{\overline{γ}(a)}^{i_{a}} = ε_{\overline{γ}(a)}. By Proposition 4.3 γ^{i_{a}} = γ^{t}, therefore ((γ(a))^{2} ∪ (γ^{t}(a))^{2})^{i_{a}} = ((γ(a))^{2} ∪ (γ^{t}(a))^{2}). All other relations from Φ(a, γ) are of the form β̂ ∪ β̂^{t}, where β̂ = β ∩ (γ(a) × γ^{t}(a)). Therefore

β̂^{i_{a}} = β^{i_{a}} ∩ (γ(a) × γ^{t}(a))^{i_{a}} = β^{t} ∩ (γ^{t}(a) × γ(a)) = (β̂)^{t},

implying that β̂ ∪ β̂^{t} is i_{a}-invariant.

Thus we have shown that all relations from Φ(a, γ) are invariant under the action of the cyclic group ⟨G_{a}, i_{a}⟩. Since the latter group acts transitively on the set \overline{γ}(a), the coherent configuration (\overline{γ}(a); ⟨Φ(a, γ)⟩) is cyclic. ♢

The algorithm for the case of d being prime is based on the following claim.

Theorem 4.1 If (X; Γ) ≅ (F_{p}; Γ_{M}), |M| = d, d an odd prime, then for any a ∈ F_{p} and any γ ∈ Γ^{∗} the relation

π_{a,γ} = i_{a} ∩ (\overline{γ}(a))^{2}

(where i_{a} is viewed as {(x, x^{i_{a}}) | x ∈ F_{p}}) is the unique basic relation ρ of the coherent configuration (\overline{γ}(a); ⟨Φ(a, γ)⟩) that satisfies the equality ρ^{2} = ε_{\overline{γ}(a)}.

In order to prove this result we need two additional statements.

Proposition 4.5 Let (F_{p}; Γ_{M}), M ≤ F_{p}^{∗}, |M| > 1 be a non-trivial cyclic association scheme. Then for each point a ∈ F_{p} and any pair of non-trivial relations α, β ∈ Γ_{M} (α(a) × β(a)) ⊄ γ for every γ ∈ Γ_{M}.

Proof. Assume the contrary, i.e., (α(a) × β(a)) ⊂ γ for some a ∈ F_{p} and α, β, γ ∈ Γ_{M}. Then p_{α,γ}^{β} = d, implying A(α)A(γ) = d A(β). According to Lemma 2.3.8 of [FarKM94] the scheme (F_{p}; Γ_{M}) should be imprimitive in this case, a contradiction. ♢

Proposition 4.5 follows also from a more general statement in [EvdP98], Lemma 5.8.

Proposition 4.6 Let S = ⟨\underline{T}_{0}, ..., \underline{T}_{r}⟩ be an S-ring over Z_{2d} with d an odd prime. Let H = 2Z_{2d} and assume that \underline{H} ∈ S and Z_{2d} \ H is not a basic set of S. Then \underline{\{d\}} ∈ S.

Proof. Let T be a basic set that contains the element d ∈ Z_{2d}. Since d is odd we have T \H ≠ ∅. This implies T ∩H = ∅. Further, we have m·d = d for each m ∈ Z_{2d}^{∗}. Therefore mT ∩ T ≠ ∅ for all m ∈ Z_{2d}^{∗}. By Theorem 23.9 of [Wie64], mT is a basic set of S. Hence mT = T for every m ∈ Z_{2d}^{∗}. Note that Z_{2d} \ H = Z_{2d}^{∗} ∪ {d}. It follows that 1 ∈ T would imply T = Z_{2d}\H, which contradicts our assumption. Thus, 1 ∉ T. However, x ∈ T, x ≠ d implies x ∈ Z_{2d}^{∗}, and therefore x^{l} ∈ T for arbitrary l. This contradicts 1 ∉ T. Thus, T = {d}, as desired. ♢

Now we are ready to prove Theorem 4.1.

Proof of Theorem 4.1. According to Proposition 4.4, (\overline{γ}(a); ⟨Φ(a, γ)⟩) is a cyclic coherent configuration on 2d points. Let g be a generator of the cyclic group ⟨\overline{G}_{a}, \overline{i}_{a}⟩ (here ^{−} means the restriction on the subset \overline{γ}(a)) and let S = log_{g}(⟨Φ(a, γ)⟩) be the corresponding S-ring over Z_{2d}. Since ⟨Φ(a, γ)⟩ contains the equivalence relation (γ(a))^{2} ∪ (γ^{t}(a))^{2}, the equivalence classes of which have size d, the subgroup 2Z_{2d} of Z_{2d} is in S.

We claim that Z_{2d} \ 2Z_{2d} cannot be a basic set of S. Indeed, if Z_{2d} \ 2Z_{2d} is a basic set of S, then

exp_{g}(Z_{2d} \ 2Z_{2d}) = (\overline{γ}(a))^{2} \ ((γ(a))^{2} ∪ (γ^{t}(a))^{2})
= (γ(a) × γ^{t}(a)) ∪ (γ^{t}(a) × γ(a))

is a basic relation of ⟨Φ(a, γ)⟩. Take any pair (x, y) ∈ γ(a)×γ^{t}(a). Let α ∈ Γ_{M}^{∗} be the basic relation that contains (x, y). Then (x, y) ∈ α ∩ (γ(a) × γ^{t}(a)) = α̂. But α̂ ∪ α̂^{t} is a union of basic relations from ⟨Φ(a, γ)⟩. Since (x, y) belongs to the basic relation (γ(a) × γ^{t}(a)) ∪ (γ^{t}(a) × γ(a)), we have

(γ(a) × γ^{t}(a)) ∪ (γ^{t}(a) × γ(a)) ⊂ α̂ ∪ α̂^{t} =
(α ∩ (γ(a) × γ^{t}(a))) ∪ (α^{t} ∩ (γ^{t}(a) × γ(a))) .

The latter inclusion implies γ(a) × γ^{t}(a) ⊂ α contrary to Proposition 4.5.

Thus, we have shown that 2Z_{2d} ∈ S and Z_{2d} \ 2Z_{2d} is not a basic set of S. By Proposition 4.6 \{d\} is a basic set of S. Therefore \{(x, x^{g^{d}}) | x ∈ \overline{γ}(a)\} is a basic relation ⟨Φ(a, γ)⟩. However, this set equals π_{a,γ}. The remaining part of the proof follows from the fact that {d} is the unique basic set T of S that satisfies T^{2} = {0}. ♢

Now we can formulate how to proceed in the case of d being prime. First, for each a ∈ X and γ ∈ Γ we use the WL-algorithm in order to find the set of basic relations of the coherent configuration (\overline{γ}(a); ⟨Φ(a, γ)⟩). If this configuration is not homogeneous, then the scheme (X; Γ) is not cyclic.

If (\overline{γ}(a); ⟨Φ(a, γ)⟩) is homogeneous, then we find all basic relations ρ ⊂ (\overline{γ}(a))^{2} that satisfies the equality ρ^{2} = ε_{\overline{γ}(a)}. If for some a ∈ X and γ ∈ Γ the number of such relations is different from 1, then (X; Γ) is not cyclic.

Thus we may assume that for each a ∈ X and every γ ∈ Γ there exists a unique involution ρ_{a,\overline{γ}(a)} ∈ Sym(\overline{γ}(a)) with ρ_{a,\overline{γ}(a)} ∈ ⟨Φ(a, γ)⟩. Write Γ = \{ε_{X}, γ_{1}, γ_{1}^{t}, ..., γ_{l}, γ_{l}^{t}\}. For each point a ∈ X define i_{a} ∈ Sym(X) as follows a^{i_{a}} = a and b^{i_{a}} = ρ_{a,\overline{γ}_{j}(a)}(b), b ≠ a where γ_{j} is defined by the inclusion b ∈ (γ_{j}(a) ∩ γ_{j}^{t}(a)). Now we take the product g = i_{a}i_{b} for some a, b ∈ X, a ≠ b. If g is a full cycle and is an automorphism of (X; Γ), then we are done, otherwise (X; Γ) is not cyclic.

Note that in the case where d is prime the final step has to be performed only for two different vertices a and b.

5 The algorithm.

In this section we first give a compact description of the recognition algorithm for circulant graphs of prime order p which is based on the method developed in the last section. Afterwards we shall estimate the time complexity of the algorithm.

Algorithm CGR

Input: The adjacency matrix A of a graph G on the vertex set {0, …, p − 1}.

Step 1. (Initialization)

1.1 Apply the WL-algorithm to A and find the basic relations of the coherent configuration (X; Γ) generated by G;

1.2 If this configuration is not homogeneous, then goto Step 4 else let B = {ε_{X}, γ_{1}, …, γ_{r}} be the set of basic relations;

1.3 Define d = |γ_{1}(0)|; If |γ_{i}(0)| ≠ d for some i > 1, then goto Step 4;

1.4 If d is prime, then goto Step 3;

Step 2.1

2.1.1 Apply the WL-algorithm to (γ_{1}(0); Γ_{γ_{1}(0)}) and find the basic relations of the coherent configuration (γ_{1}(0); Γ^{γ_{1}(0)});

2.1.2 If this configuration is not homogeneous, then goto Step 4 else let B_{γ_{1}}(0) = {ε_{γ_{1}(0)}, β_{1}, …, β_{s}} be the set of basic relations;

2.1.3 Find the connected components C_{1}, …, C_{q} of (γ_{1}(0), β_{1} ∪ β_{1}^{t}); If some of these components have different size then goto Step 4 else define C_{γ_{1}}(0) = {C_{1}, …, C_{q}};

2.1.4 For α ∈ B_{γ_{1}}(0) \ {ε_{γ_{1}(0)}, β_{1}} do begin Find the connected components C_{α,1}, …, C_{α,q_{α}} of (γ_{1}(0), α ∪ α^{t}); If some of these components are of different size, then goto Step 4 else do

begin

If q_{α} > |C_{γ_{1}}(0)| then C_{γ_{1}}(0) = {C_{1}, …, C_{q_{α}}};

If q_{α} = |C_{γ_{1}}(0)| and C_{γ_{1}}(0) ≠ {C_{1}, …, C_{q_{α}}} then goto Step 4; end;

end;

Step 2.2

For x ∈ X and γ ∈ B \ {ε_{X}} do if (x, γ) ≠ (0, γ_{1}) then begin

2.2.1 Apply the WL-algorithm to (γ(x); Γ_{γ(x)}) and find the basic relations of the coherent configuration (γ(x); Γ^{γ(x)});

2.2.2 If this configuration is not homogeneous, then goto Step 4 else let B_{γ}(x) = {ε_{γ(x)}, β_{1}, …, β_{s}} be the set of basic relations;

2.2.3 Find the connected components C_{1}, …, C_{q} of (γ(x), β_{1} ∪ β_{1}^{t}); If some of these components have different size, then goto Step 4 else define C_{γ}(x) = {C_{1}, …, C_{q}};

2.2.4 For α ∈ B_{γ}(x) \ {ε_{γ(x)}, β_{1}} do begin Find the connected components C_{1}, …, C_{q_{α}} of (γ(x), α ∪ α^{t}); If some of these components are of different size, then goto Step 4 else do

begin

If q_{α} > |C_{γ}(x)|, then C_{γ}(x) = {C_{1}, …, C_{q_{α}}};

If q_{α} = |C_{γ}(x)| and C_{γ}(x) ≠ {C_{1}, …, C_{q_{α}}} then goto Step 4; end;

end; If |C_{γ}(x)| ≠ |C_{γ_{1}}(0)|, then goto Step 4; end;

Step 2.3

2.3.1 For x ∈ X define

τ_{x} = ⋃_{γ∈Γ^{∗}} ⋃_{C∈C_{γ}(x)} C × C;

2.3.2 Find the components ϕ_{1}, …, ϕ_{s} of the relation Φ on X^{2} \ ε_{X} defined in Lemma 4.2; 2.3.3 If B′ = {ε_{X}, ϕ_{1}, …, ϕ_{s}} is not the basis of an association scheme then goto

Step 4;

2.3.4 Define B = B′ and goto Step 1.3;

Step 3

For a ∈ {0, 1} do begin

3.1 For γ ∈ B do begin

3.1.1 Define

\overline{γ}(a) = γ(a) ∪ γ^{t}(a);
W (a, γ) = γ(a) × γ^{t}(a);
Γ(a, γ) = {β ∩ W (a, γ) | β ∈ Γ};
Γ̂(a, γ) = {β ∪ β^{t} |β ∈ Γ(a, γ) ∧ β ≠ ∅};
Φ(a, γ) = \{ε_{\overline{γ}(a)}, (γ(a))^{2} ∪ (γ^{t}(a))^{2}\} ∪ Γ̂(a, γ);

3.1.2 Apply the WL-algorithm to (\overline{γ}(a), Φ(a, γ)) in order to find the set of basic relations B(a, γ) for (\overline{γ}(a), ⟨Φ(a, γ)⟩)

3.1.3 If this configuration is not homogeneous, then goto Step 4;

3.1.4 Find all basic relations ρ ∈ B(a, γ) with the property ρ^{2} = ε_{\overline{γ}(a)}; If there is more than one or no such relation, then goto Step 4;

3.1.5 Let \{(y, ρ_{a,γ}(y)) : y ∈ \overline{γ}(a)\} be the unique relation found in the last step;

end;

3.2 Define the involution i_{a} by x^{i_{a}} = \{ \begin{matrix}a & if x = a \\ ρ_{a,γ}(x) & if x ∈ \overline{γ}(a); \end{matrix}

end; Goto Step 5;

Step 4

Stop; Comment: ’G is not a circulant graph’;

Step 5 Compute the permutation g = i_{0}i_{1} of X; If g is not a cyclic automorphism, then goto Step 4; Output (0, 0^{g}, …, 0^{g^{n−1}}); Stop;

Remarks:

The mapping 0^{g^{k}} → k, 0 ≤ k ≤ p − 1 defines a Cayley numbering of the input graph.

Note that the steps 2.1 to 2.3 correspond to Step 1 to Step 3 in Subsection 4.1. The most time consuming step in Algorithm CGR is Step 2 which is the iteration step. Its complexity is O(p^{5} ln(p)). Since d decreases to at least \frac{d}{2} in each iteration the overall worst case time complexity of the algorithm is at most O(p^{5} ln(p)^{2}).

6 Examples

To see how the algorithm works let us discuss some examples.

Figure 1  Figure 2

Example 1: Consider the graph in Figure 1. Its coherent configuration has adjacency matrix

Adj(A) = ( \begin{matrix}0 & 4 & 3 & 1 & 2 & 2 & 1 & 6 & 5 & 5 & 6 & 3 & 4 \\ 4 & 0 & 2 & 5 & 3 & 2 & 6 & 3 & 1 & 4 & 1 & 6 & 5 \\ 3 & 2 & 0 & 3 & 5 & 4 & 5 & 4 & 1 & 2 & 6 & 1 & 6 \\ 1 & 5 & 3 & 0 & 1 & 6 & 2 & 2 & 3 & 4 & 4 & 5 & 6 \\ 2 & 3 & 5 & 1 & 0 & 4 & 6 & 1 & 3 & 6 & 5 & 4 & 2 \\ 2 & 2 & 4 & 6 & 4 & 0 & 1 & 5 & 6 & 3 & 1 & 5 & 3 \\ 1 & 6 & 5 & 2 & 6 & 1 & 0 & 4 & 4 & 3 & 2 & 3 & 5 \\ 6 & 3 & 4 & 2 & 1 & 5 & 4 & 0 & 5 & 2 & 3 & 6 & 1 \\ 5 & 1 & 1 & 3 & 3 & 6 & 4 & 5 & 0 & 6 & 2 & 2 & 4 \\ 5 & 4 & 2 & 4 & 6 & 3 & 3 & 2 & 6 & 0 & 5 & 1 & 1 \\ 6 & 1 & 6 & 4 & 5 & 1 & 2 & 3 & 2 & 5 & 0 & 4 & 3 \\ 3 & 6 & 1 & 5 & 4 & 5 & 3 & 6 & 2 & 1 & 4 & 0 & 2 \\ 4 & 5 & 6 & 6 & 2 & 3 & 5 & 1 & 4 & 1 & 3 & 2 & 0 \end{matrix} ) .

Since the diagonal is uniformly colored, the coherent configuration is homogeneous. We have six non-trivial symmetric basic relations. Each of the corresponding basic graphs has degree 2. Consider the first basic relation γ_{1}. It is the union of two antiparallel cycles

(0, 3, 4, 7, 12, 9, 11, 2, 8, 1, 10, 5, 6), (0, 6, 5, 10, 1, 8, 2, 11, 9, 12, 7, 4, 3).

Renumbering the vertices according to

0 ⟶ 0, 3 ⟶ 1, 4 ⟶ 2, 7 ⟶ 3, 12 ⟶ 4, 9 ⟶ 5, 11 ⟶ 6, 2 ⟶ 7,

8 ⟶ 8, 1 ⟶ 9, 10 ⟶ 10, 5 ⟶ 11, 6 ⟶ 12

and rearranging the vertices along a cycle changes the graph in Figure 1 into the graph in Figure 2. Note that each of the other basic graphs defines a full cyclic automorphism, too.

Example 2: The graph in Figure 3 is the same as in Figure 1, however, some of its edges are oriented. The remaining non-oriented edges are considered to be pairs of anti-parallel oriented edges. The adjacency matrix of the associated coherent configuration is

Adj(A) = ( \begin{matrix}0 & 5 & 7 & 1 & 2 & 3 & 11 & 12 & 8 & 9 & 10 & 6 & 4 \\ 4 & 0 & 3 & 9 & 6 & 2 & 12 & 7 & 11 & 5 & 1 & 10 & 8 \\ 6 & 2 & 0 & 7 & 8 & 4 & 9 & 5 & 1 & 3 & 12 & 11 & 10 \\ 11 & 8 & 6 & 0 & 1 & 10 & 3 & 2 & 7 & 4 & 5 & 9 & 12 \\ 3 & 7 & 9 & 11 & 0 & 5 & 10 & 1 & 6 & 12 & 8 & 4 & 2 \\ 2 & 3 & 5 & 12 & 4 & 0 & 1 & 9 & 10 & 7 & 11 & 8 & 6 \\ 1 & 10 & 8 & 2 & 12 & 11 & 0 & 4 & 5 & 6 & 3 & 7 & 9 \\ 10 & 6 & 4 & 3 & 11 & 8 & 5 & 0 & 9 & 2 & 7 & 12 & 1 \\ 9 & 1 & 11 & 6 & 7 & 12 & 4 & 8 & 0 & 10 & 2 & 3 & 5 \\ 8 & 4 & 2 & 5 & 10 & 6 & 7 & 3 & 12 & 0 & 9 & 1 & 11 \\ 12 & 11 & 10 & 4 & 9 & 1 & 2 & 6 & 3 & 8 & 0 & 5 & 7 \\ 7 & 12 & 1 & 8 & 5 & 9 & 6 & 10 & 2 & 11 & 4 & 0 & 3 \\ 5 & 9 & 12 & 10 & 3 & 7 & 8 & 11 & 4 & 1 & 6 & 2 & 0 \end{matrix} ) .

Obviously, the configuration is homogeneous. All basic relations are full cycles. Take for instance γ_{7}. The corresponding cycle is

(0, 2, 3, 8, 4, 1, 7, 10, 12, 5, 9, 6, 11).

Renumbering the vertices according to

0 ⟶ 0, 2 ⟶ 1, 3 ⟶ 2, 8 ⟶ 3, 4 ⟶ 4, 1 ⟶ 5, 7 ⟶ 6,
10 ⟶ 7, 12 ⟶ 8, 5 ⟶ 9, 9 ⟶ 10, 6 ⟶ 11, 11 ⟶ 12,

and rearranging the vertices along a cycle changes the graph of Figure 3 into the graph of Figure 4.

Example 3: Consider the digraph in Figure 5. It looks like a circulant graph. What is the appropriate numbering of the vertices?

The adjacency matrix of the corresponding coherent configuration is given below. The configuration is homogeneous. Each basic graph has outdegree 3. Hence, we are in the case where d is a prime. Therefore, we have to perform Step 3 of the algorithm. We have γ_{3} = γ_{1}^{t} and γ_{4} = γ_{2}^{t}. Further,

\overline{γ}_{1}(0) = \{1, 3, 7\} ∪ \{6, 10, 12\}, \overline{γ}_{2}(0) = \{4, 9, 11\} ∪ \{2, 5, 8\}

\overline{γ}_{1}(1) = \{6, 9, 10\} ∪ \{0, 8, 11\}, \overline{γ}_{2}(1) = \{3, 4, 5\} ∪ \{2, 7, 12\}.

Adj(A) = ( \begin{matrix}0 & 1 & 4 & 1 & 2 & 4 & 3 & 1 & 4 & 2 & 3 & 2 & 3 \\ 3 & 0 & 4 & 2 & 2 & 2 & 1 & 4 & 3 & 1 & 1 & 3 & 4 \\ 2 & 2 & 0 & 4 & 4 & 3 & 2 & 1 & 1 & 4 & 1 & 3 & 3 \\ 3 & 4 & 2 & 0 & 1 & 3 & 4 & 2 & 4 & 3 & 1 & 2 & 1 \\ 4 & 4 & 2 & 3 & 0 & 1 & 3 & 1 & 2 & 1 & 4 & 3 & 2 \\ 2 & 4 & 1 & 1 & 3 & 0 & 1 & 2 & 3 & 4 & 3 & 4 & 2 \\ 1 & 3 & 4 & 2 & 1 & 3 & 0 & 3 & 1 & 2 & 4 & 4 & 2 \\ 3 & 2 & 3 & 4 & 3 & 4 & 1 & 0 & 2 & 2 & 4 & 1 & 1 \\ 2 & 1 & 3 & 2 & 4 & 1 & 3 & 4 & 0 & 3 & 2 & 4 & 1 \\ 4 & 3 & 2 & 1 & 3 & 2 & 4 & 4 & 1 & 0 & 2 & 1 & 3 \\ 1 & 3 & 3 & 3 & 2 & 1 & 2 & 2 & 4 & 4 & 0 & 1 & 4 \\ 4 & 1 & 1 & 4 & 1 & 2 & 2 & 3 & 2 & 3 & 3 & 0 & 4 \\ 1 & 2 & 1 & 3 & 4 & 4 & 4 & 3 & 3 & 1 & 2 & 2 & 0 \end{matrix} ) .

The adjaceny matrices A(a, j) of the configurations generated by the sets of relations ⟨Φ(a, γ_{j})⟩, a ∈ {0, 1}, j ∈ {1, 2} are

A(0, 1) = ( \begin{matrix}0 & 3 & 3 & 1 & 1 & 2 \\ 3 & 0 & 3 & 2 & 1 & 1 \\ 3 & 3 & 0 & 1 & 2 & 1 \\ 1 & 2 & 1 & 0 & 3 & 3 \\ 1 & 1 & 2 & 3 & 0 & 3 \\ 2 & 1 & 1 & 3 & 3 & 0 \end{matrix} ) , A(0, 2) = ( \begin{matrix}0 & 3 & 3 & 2 & 1 & 2 \\ 3 & 0 & 3 & 2 & 2 & 1 \\ 3 & 3 & 0 & 1 & 2 & 2 \\ 2 & 2 & 1 & 0 & 3 & 3 \\ 1 & 2 & 2 & 3 & 0 & 3 \\ 2 & 1 & 2 & 3 & 3 & 0 \end{matrix} ) ,

A(1, 1) = ( \begin{matrix}0 & 3 & 3 & 1 & 1 & 2 \\ 3 & 0 & 3 & 2 & 1 & 1 \\ 3 & 3 & 0 & 1 & 2 & 1 \\ 1 & 2 & 1 & 0 & 3 & 3 \\ 1 & 1 & 2 & 3 & 0 & 3 \\ 2 & 1 & 1 & 3 & 3 & 0 \end{matrix} ) , A(1, 2) = ( \begin{matrix}0 & 3 & 3 & 2 & 2 & 1 \\ 3 & 0 & 3 & 2 & 1 & 2 \\ 3 & 3 & 0 & 1 & 2 & 2 \\ 2 & 2 & 1 & 0 & 3 & 3 \\ 2 & 1 & 2 & 3 & 0 & 3 \\ 1 & 2 & 2 & 3 & 3 & 0 \end{matrix} ) .

We find the following involutions:

i_{0} : (1, 12)(3, 6)(7, 10)(4, 5)(9, 8)(11, 2),

the electronic journal of combinatorics 3 (1996), #Rxx 23

i_{1} : (6, 11)(9, 0)(10, 8)(3, 12)(4, 7)(5, 2).

Thus, i_{0}i_{1} gives the cyclic permutation (0, 8, 7, 5, 11, 3, 1, 12, 6, 2, 4, 10, 9).

Figure 7  Figure 8

Renumbering the vertices according to

0 ⟶ 0, 8 ⟶ 1, 7 ⟶ 2, 5 ⟶ 3, 11 ⟶ 4, 3 ⟶ 5, 1 ⟶ 6,

12 ⟶ 7, 6 ⟶ 8, 2 ⟶ 9, 4 ⟶ 10, 10 ⟶ 11, 9 ⟶ 12

changes the graph in Figure 5 to the graph in Figure 6. Example 4: Consider the graph in Figure 7. Its associated coherent configuration has adjacency matrix

Adj(A) = ( \begin{matrix}0 & 1 & 2 & 3 & 3 & 2 & 1 & 1 & 3 & 2 & 3 & 2 & 1 \\ 1 & 0 & 2 & 1 & 3 & 1 & 3 & 2 & 2 & 3 & 3 & 1 & 2 \\ 2 & 2 & 0 & 1 & 2 & 1 & 1 & 1 & 3 & 3 & 2 & 3 & 3 \\ 3 & 1 & 1 & 0 & 2 & 2 & 3 & 2 & 1 & 3 & 1 & 2 & 3 \\ 3 & 3 & 2 & 2 & 0 & 1 & 1 & 3 & 1 & 2 & 1 & 3 & 2 \\ 2 & 1 & 1 & 2 & 1 & 0 & 2 & 3 & 2 & 3 & 3 & 3 & 1 \\ 1 & 3 & 1 & 3 & 1 & 2 & 0 & 2 & 3 & 1 & 2 & 3 & 2 \\ 1 & 2 & 1 & 2 & 3 & 3 & 2 & 0 & 3 & 2 & 1 & 1 & 3 \\ 3 & 2 & 3 & 1 & 1 & 2 & 3 & 3 & 0 & 2 & 2 & 1 & 1 \\ 2 & 3 & 3 & 3 & 2 & 3 & 1 & 2 & 2 & 0 & 1 & 1 & 1 \\ 3 & 3 & 2 & 1 & 1 & 3 & 2 & 1 & 2 & 1 & 0 & 2 & 3 \\ 2 & 1 & 3 & 2 & 3 & 3 & 3 & 1 & 1 & 1 & 2 & 0 & 2 \\ 1 & 2 & 3 & 3 & 2 & 1 & 2 & 3 & 1 & 1 & 3 & 2 & 0 \end{matrix} ) .

The configuration is homogeneous. There are three symmetric non-trivial basic relations γ_{1}, γ_{2} and γ_{3}, each of non-prime degree 4. Let us perform Step 2 of the algorithm. The first table below shows the sets γ_{i}(a):

γ_{1}  γ_{2}  γ_{3}
0 1,6,7,12 2,5,9,11 3,4,8,10
1 0,3,5,11 2,7,8,12 4,6,9,10
2 3,5,6,7 0,1,4,10 8,9,11,12
3 1,2,8,10 4,5,7,11 0,6,9,12
4 5,6,8,10 2,3,9,12 0,1,7,11
5 1,2,4,12 0,3,6,8 7,9,10,11
6 0,2,4,9 5,7,10,12 1,3,8,11
7 0,2,10,11 1,3,6,9 4,5,8,12
8 3,4,11,12 1,5,9,10 0,2,6,7
9 6,10,11,12 0,4,7,8 1,2,3,5
10 3,4,7,9 2,6,8,11 0,1,5,12
11 1,7,8,9 0,3,10,12 2,4,5,6
12 0,5,8,9 1,4,6,11 2,3,7,10

Vertex  Classes
0  {0}, {1, 6}, {2, 5}, {3, 4}, {7, 12}, {8, 10}, {9, 11}
1  {1}, {0, 3}, {2, 7}, {4, 9}, {5, 11}, {6, 10}, {8, 12}
2  {2}, {0, 1}, {3, 6}, {4, 10}, {5, 7}, {8, 9}, {11, 12}
3  {3}, {0, 9}, {1, 10}, {2, 8}, {4, 5}, {6, 12}, {7, 11}
4  {4}, {0, 11}, {1, 7}, {2, 3}, {5, 10}, {6, 8}, {9, 12}
5  {5}, {0, 6}, {1, 4}, {2, 12}, {3, 8}, {7, 9}, {10, 11}
6  {6}, {0, 4}, {1, 8}, {2, 9}, {3, 11}, {5, 12}, {7, 10}
7  {7}, {0, 10}, {1, 3}, {2, 11}, {4, 12}, {5, 8}, {6, 9}
8  {8}, {0, 2}, {1, 5}, {3, 12}, {4, 11}, {6, 7}, {9, 10}
9  {9}, {0, 7}, {1, 2}, {3, 5}, {4, 8}, {6, 11}, {10, 12}
10 {10}, {0, 5}, {1, 12}, {2, 6}, {3, 9}, {4, 7}, {8, 11}
11 {11}, {0, 12}, {1, 9}, {2, 4}, {3, 10}, {5, 6}, {7, 8}
12 {12}, {0, 8}, {1, 11}, {2, 10}, {3, 7}, {4, 6}, {5, 9}

For a matrix A and a set W of indices write A_{W} for the submatrix of A consisting of all rows and columns index with elements of W. It is easy to see by inspection that each of the blocks Adj(A)_{γ_{i}(a)} is of one of the following forms

( \begin{matrix}0 & x & y & y \\ x & 0 & y & y \\ y & y & 0 & x \\ y & y & x & 0 \end{matrix} ) , ( \begin{matrix}0 & x & y & x \\ x & 0 & x & y \\ y & x & 0 & x \\ x & y & x & 0 \end{matrix} ) , ( \begin{matrix}0 & x & x & y \\ x & 0 & y & x \\ x & y & 0 & x \\ y & x & x & 0 \end{matrix} ) ,

where x, y ∈ {1, 2, 3}, x ≠ y. Using this we find the equivalence relations given in the second table above. Now, this table at hand, determining the components of Φ according to Lemma 4.2 is straight-forward. We get 6 components, which are represented by the following joint adjacency matrix:

( \begin{matrix}0 & 1 & 3 & 5 & 5 & 3 & 1 & 2 & 6 & 4 & 6 & 4 & 2 \\ 1 & 0 & 3 & 1 & 6 & 2 & 5 & 3 & 4 & 6 & 5 & 2 & 4 \\ 3 & 3 & 0 & 2 & 4 & 1 & 2 & 1 & 6 & 6 & 4 & 5 & 5 \\ 5 & 1 & 2 & 0 & 4 & 4 & 6 & 3 & 2 & 5 & 1 & 3 & 6 \\ 5 & 6 & 4 & 4 & 0 & 2 & 1 & 6 & 1 & 3 & 2 & 5 & 3 \\ 3 & 2 & 1 & 4 & 2 & 0 & 3 & 5 & 4 & 5 & 6 & 6 & 1 \\ 1 & 5 & 2 & 6 & 1 & 3 & 0 & 4 & 5 & 2 & 4 & 6 & 3 \\ 2 & 3 & 1 & 3 & 6 & 5 & 4 & 0 & 5 & 4 & 2 & 1 & 6 \\ 6 & 4 & 6 & 2 & 1 & 4 & 5 & 5 & 0 & 3 & 3 & 1 & 2 \\ 4 & 6 & 6 & 5 & 3 & 5 & 2 & 4 & 3 & 0 & 1 & 2 & 1 \\ 6 & 5 & 4 & 1 & 2 & 6 & 4 & 2 & 3 & 1 & 0 & 3 & 5 \\ 4 & 2 & 5 & 3 & 5 & 6 & 6 & 1 & 1 & 2 & 3 & 0 & 4 \\ 2 & 4 & 5 & 6 & 3 & 1 & 3 & 6 & 2 & 1 & 5 & 4 & 0 \end{matrix} ) .

In addition, this matrix is already the adjacency matrix of the coherent configuration generated by the components of Φ. The configuration is homogeneous. We have six non-trivial basic relations of degree d = 2 each. Each of them defines an undirected cycle, i.e. a full cycle and its inverse. For instance, γ_{1} defines the cycle

(0, 1, 3, 10, 9, 12, 5, 2, 7, 11, 8, 4, 6).

Renumbering the vertices of the graph according to

0 ⟶ 0, 1 ⟶ 1, 3 ⟶ 2, 10 ⟶ 3, 9 ⟶ 4, 12 ⟶ 5, 5 ⟶ 6,
2 ⟶ 7, 7 ⟶ 8, 11 ⟶ 9, 8 ⟶ 10, 4 ⟶ 11, 6 ⟶ 12

changes the picture of the graph in Figure 7 to the one in Figure 8.

Example 5: Not every association scheme on a prime number of vertices is cyclic. To have an example consider the adjacency matrix below. It is the adjacency matrix of a homogeneous and commutative coherent configuration generated by an antisymmetric strongly regular graph Γ on 23 vertices. However, the automorphism group of this scheme is not transitive. Changing the first diagonal entry from 0 to 3 and applying the WL-algorithm to the resulting matrix yields a coherent configuration with 17 basic relations, while changing the second diagonal entry from 0 to 3 and applying the WL-algorithm yields 113 basic relations. This proves that 0 and 1 are not in the same orbit. Our algorithm, applied to the above matrix, will perform Step 1 and afterwards turn to Step 3. It will decide that the input is not cyclic at the first arrival at 3.1.4.

( \begin{matrix}0 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 0 & 2 & 1 & 2 & 2 & 2 & 1 & 1 & 1 & 2 & 1 & 2 & 1 & 2 & 1 & 1 & 1 & 2 & 2 & 2 & 1 & 2 \\ 1 & 1 & 0 & 2 & 1 & 2 & 2 & 2 & 1 & 1 & 1 & 2 & 2 & 2 & 1 & 2 & 1 & 1 & 1 & 2 & 2 & 2 & 1 \\ 1 & 2 & 1 & 0 & 2 & 1 & 2 & 2 & 2 & 1 & 1 & 1 & 1 & 2 & 2 & 1 & 2 & 1 & 1 & 1 & 2 & 2 & 2 \\ 1 & 1 & 2 & 1 & 0 & 2 & 1 & 2 & 2 & 2 & 1 & 1 & 2 & 1 & 2 & 2 & 1 & 2 & 1 & 1 & 1 & 2 & 2 \\ 1 & 1 & 1 & 2 & 1 & 0 & 2 & 1 & 2 & 2 & 2 & 1 & 2 & 2 & 1 & 2 & 2 & 1 & 2 & 1 & 1 & 1 & 2 \\ 1 & 1 & 1 & 1 & 2 & 1 & 0 & 2 & 1 & 2 & 2 & 2 & 2 & 2 & 2 & 1 & 2 & 2 & 1 & 2 & 1 & 1 & 1 \\ 1 & 2 & 1 & 1 & 1 & 2 & 1 & 0 & 2 & 1 & 2 & 2 & 1 & 2 & 2 & 2 & 1 & 2 & 2 & 1 & 2 & 1 & 1 \\ 1 & 2 & 2 & 1 & 1 & 1 & 2 & 1 & 0 & 2 & 1 & 2 & 1 & 1 & 2 & 2 & 2 & 1 & 2 & 2 & 1 & 2 & 1 \\ 1 & 2 & 2 & 2 & 1 & 1 & 1 & 2 & 1 & 0 & 2 & 1 & 1 & 1 & 1 & 2 & 2 & 2 & 1 & 2 & 2 & 1 & 2 \\ 1 & 1 & 2 & 2 & 2 & 1 & 1 & 1 & 2 & 1 & 0 & 2 & 2 & 1 & 1 & 1 & 2 & 2 & 2 & 1 & 2 & 2 & 1 \\ 1 & 2 & 1 & 2 & 2 & 2 & 1 & 1 & 1 & 2 & 1 & 0 & 1 & 2 & 1 & 1 & 1 & 2 & 2 & 2 & 1 & 2 & 2 \\ 2 & 1 & 1 & 2 & 1 & 1 & 1 & 2 & 2 & 2 & 1 & 2 & 0 & 1 & 2 & 1 & 1 & 1 & 2 & 2 & 2 & 1 & 2 \\ 2 & 2 & 1 & 1 & 2 & 1 & 1 & 1 & 2 & 2 & 2 & 1 & 2 & 0 & 1 & 2 & 1 & 1 & 1 & 2 & 2 & 2 & 1 \\ 2 & 1 & 2 & 1 & 1 & 2 & 1 & 1 & 1 & 2 & 2 & 2 & 1 & 2 & 0 & 1 & 2 & 1 & 1 & 1 & 2 & 2 & 2 \\ 2 & 2 & 1 & 2 & 1 & 1 & 2 & 1 & 1 & 1 & 2 & 2 & 2 & 1 & 2 & 0 & 1 & 2 & 1 & 1 & 1 & 2 & 2 \\ 2 & 2 & 2 & 1 & 2 & 1 & 1 & 2 & 1 & 1 & 1 & 2 & 2 & 2 & 1 & 2 & 0 & 1 & 2 & 1 & 1 & 1 & 2 \\ 2 & 2 & 2 & 2 & 1 & 2 & 1 & 1 & 2 & 1 & 1 & 1 & 2 & 2 & 2 & 1 & 2 & 0 & 1 & 2 & 1 & 1 & 1 \\ 2 & 1 & 2 & 2 & 2 & 1 & 2 & 1 & 1 & 2 & 1 & 1 & 1 & 2 & 2 & 2 & 1 & 2 & 0 & 1 & 2 & 1 & 1 \\ 2 & 1 & 1 & 2 & 2 & 2 & 1 & 2 & 1 & 1 & 2 & 1 & 1 & 1 & 2 & 2 & 2 & 1 & 2 & 0 & 1 & 2 & 1 \\ 2 & 1 & 1 & 1 & 2 & 2 & 2 & 1 & 2 & 1 & 1 & 2 & 1 & 1 & 1 & 2 & 2 & 2 & 1 & 2 & 0 & 1 & 2 \\ 2 & 2 & 1 & 1 & 1 & 2 & 2 & 2 & 1 & 2 & 1 & 1 & 2 & 1 & 1 & 1 & 2 & 2 & 2 & 1 & 2 & 0 & 1 \\ 2 & 1 & 2 & 1 & 1 & 1 & 2 & 2 & 2 & 1 & 2 & 1 & 1 & 2 & 1 & 1 & 1 & 2 & 2 & 2 & 1 & 2 & 0 \end{matrix} ) .

The example considered here is from an infinite series of examples of non-cyclic association schemes. It is found by the so-called doubling method described in [FarKM94], Theorem 2.6.6. A different way to arrive at this example is by using the one-to-one correspondence between skew-symmetric Hadamard matrices of order 4n and association schemes with two non-symmetric classes on 4n-1 points (regular tournaments) described in [Ito84].

7 Concluding remarks.

The described algorithm is based on the fact that the automorphism group of any circulant association scheme on p points is a Frobenius group. There is a more general class of association schemes the automorphism group of which is a Frobenius group, namely: the cyclotomic schemes on p^{n} points. So one can try to modify the algorithm in order to recognize this class of schemes. Results in this direction will be published in a forthcoming paper.

8 Acknowledgment

The authors wish to express their gratitude to the anonymous referee for pointing out some inconsistencies in the first draft of the paper and for giving various valuable suggestions and remarks.

References

[BBLT97] L. Babel, S. Baumann, M. Lüdecke, G. Tinhofer, STABCOL: Graph isomorphism testing based on the Weisfeiler-Leman algorithm. Preprint. TUM-M9702, Munich, 1997, 33 pp.

[BCKP97] L. Babel, I.V. Chuvaeva, M. Klin, D.V. Pasechnik, Algebraic Combinatorics in Mathematical Chemistry. Methods and Algorithms. II. Program implementation of the Weisfeiler-Leman algorithm. (A preliminary version). Preprint. TUM-M9701, Munich, 1997, 45 pp.

[BaI84] E. Bannai, T. Ito, Algebraic Combinatorics I, Association Schemes. Benjamin/Cummings, Menlo Park 1984

[BaS93] E. Bannai, Y. S. Song, Character table of fission schemes and fusion schemes. Europ. J. of Combin. 14, (1993), 385-396.

[EvdP98] S. Evdokimov, I. Ponomarenko, On Primitive Cellular Algebras. Zapiski POMI, 1998, to appear.

[FarIK92] I. A. Faradžev, A. A. Ivanov, M. H. Klin, Galois correspondence between permutation groups and cellular rings (association schems). Graphs and Comb. 6, (1992), 202-224.

[FarKM94] I. A. Faradžev, M. H. Klin, M. E. Muzychuk, Cellular rings and groups of automorphisms of graphs. In: Faradžev I.A. et al. (eds.): Investigations in algebraic theory of combinatorial objects. Kluwer Acad. Publ., Dordrecht, 1994, 1-152.

[Hig70] D. G. Higman, Coherent configurations. I. Rend. Sem. Mat. Univ. Padova 44, (1970), 1-25.

[Hig87] D. G. Higman, Coherent algebras. Linear Algebra Appl. 93, (1987), 209-239.

[Ito84] N. Ito, Tournaments with transitive automorphism group. Europ. J. of Comb. 5, (1984), 37-42.

[KliP78] M. Ch. Klin, R. Pöschel, The König problem, the isomorphism problem for cyclic graphs and the characterization of Schur rings. Report Zentralinst. für Math.und Mech., Akademie der Wissenschaften der DDR, Berlin, 1978.

[McC63] R. McConnel, Pseudo-ordered polynomial over a finite field. Acta Arith. 8, (1963), 127-151.

[Pon92] I. Ponomarenko, Polynomial-Time Algorithms for Recognizing and Isomorphism Testing of Cyclic Tournaments. Acta Appl. Math. 29, (1992), 139-160.

[Wei76] B. J. Weisfeiler (Ed.), On construction and identification of graphs, Springer Lecture Notes 558 (1976).

[Wie64] H. W. Wielandt, Finite permutation groups. Academic Press, N.Y.,