Martiniano Eguía

Francisco J Soulignac

Hereditary biclique-Helly graphs: recognition and maximal biclique enumeration

Keywords: hereditary biclique-Helly graphs, maximal bicliques, triangle-free graphs, domination problems

A biclique is a set of vertices that induce a complete bipartite graph. A graph G is biclique-Helly when its family of maximal bicliques satisfies the Helly property. If every induced subgraph of G is also biclique-Helly, then G is hereditary biclique-Helly. A graph is C4-dominated when every cycle of length 4 contains a vertex that is dominated by the vertex of the cycle that is not adjacent to it. In this paper we show that the class of hereditary biclique-Helly graphs is formed precisely by those C4-dominated graphs that contain no triangles and no induced cycles of length either 5 or 6. Using this characterization, we develop an algorithm for recognizing hereditary biclique-Helly graphs in O(n 2 + αm) time and O(n + m) space. (Here n, m, and α = O(m 1/2 ) are the number of vertices and edges, and the arboricity of the graph, respectively.) As a subprocedure, we show how to recognize those C4-dominated graphs that contain no triangles in O(αm) time and O(n + m) space. Finally, we show how to enumerate all the maximal bicliques of a C4-dominated graph with no triangles in O(n 2 + αm) time and O(αm) space.

Introduction

A family of sets satisfies the Helly property, or simply is a Helly family, if for every subfamily F of pairwise intersecting sets there is an element common to all the sets in F. The Helly property plays a central role in the study of clique graphs [START_REF] Mitre | Complexity aspects of the Helly property: graphs and hypergraphs[END_REF][START_REF] Mckee | Topics in intersection graph theory[END_REF][START_REF] Luiz | A survey on clique graphs[END_REF]. In the last years, several concepts that are widely studied for cliques have been translated in terms of bicliques [START_REF] Groshaus | Bicliques, cliques, neighborhoods, and the Helly property[END_REF][START_REF] Groshaus | On the iterated biclique operator[END_REF][START_REF] Groshaus | The number of convergent graphs under the biclique operator with no twin vertices is finite[END_REF][START_REF] Groshaus | On hereditary Helly classes of graphs[END_REF][START_REF] Groshaus | Biclique-Helly graphs[END_REF][START_REF] Groshaus | Biclique graphs and biclique matrices[END_REF][START_REF] Montero | Convergencia y divergencia del grafo biclique iterado[END_REF][START_REF] Terlisky | Biclique-coloreo de grafos[END_REF]. In the process, the classes of biclique-Helly and hereditary biclique-Helly graphs were first studied.

A graph is biclique-Helly when its family of maximal bicliques is Helly. A biclique-Helly graph can be obtained from any bipartite graph by inserting a vertex adjacent to all the vertices in one bipartition. Thus, induced subgraphs of a biclique-Helly graph need not be biclique-Helly. Hereditary biclique-Helly graphs are defined as those graphs whose induced subgraphs are all biclique-Helly. Hereditary biclique-Helly graphs were studied by Groshaus and Szwarcfiter, who characterized them by a family of six forbidden induced subgraphs with at most 8 vertices [START_REF] Groshaus | On hereditary Helly classes of graphs[END_REF]. This characterization implies a polynomial recognition algorithm for hereditary biclique-Helly graphs, though the most efficient algorithm to this date takes O(n 3 m 2 ) time (cf. [START_REF] Mitre | Complexity aspects of the Helly property: graphs and hypergraphs[END_REF]).

The problem of enumerating all the maximal bicliques of a graph is widely studied both for general graphs and for bipartite graphs (e.g. [START_REF] Vânia | Generating bicliques of a graph in lexicographic order[END_REF][START_REF] Gély | Enumeration aspects of maximal cliques and bicliques[END_REF][START_REF] Makino | New algorithms for enumerating all maximal cliques[END_REF][START_REF] Nourine | A fast algorithm for building lattices[END_REF]). Since a biclique-Helly graph can be obtained from any bipartite graph by inserting a vertex, any algorithm that enumerates the maximal bicliques of a biclique-Helly graph can also be used to enumerate all the maximal bicliques of a general bipartite graph. Since bipartite graphs can can have an exponential number of bicliques (see [START_REF] Prisner | Bicliques in graphs. I. Bounds on their number[END_REF]), enumerating the maximal bicliques of a biclique-Helly graph can require an exponential amount of time.

In this paper we focus on two problems for hereditary biclique-Helly graphs: their recognition and the enumeration of maximal bicliques. For the recognition problem, we rephrase the characterization by Groshaus and Szwarcfiter in more algorithmic terms and, using this new characterization, we develop an O(αm + n 2 ) time and O(n + m) space recognition algorithm, where α < √ m is the arboricity of the graph. As one of the steps in our algorithm, we require the recognition of a larger class, formed by all the triangle-free graphs whose C 4 's have at least one vertex dominated by other vertex of the cycle. We call this class, the class of C 4 -dominated graphs with no triangles. We develop a recognition algorithm for this class that takes O(αm) time and O(n + m) space. For the enumeration of maximal bicliques, we develop an O(αm + o) time and space algorithm that outputs all the bicliques of any triangle-free C 4 -dominated graph, where o < n 2 is the size of the output. Furthermore, we prove that every maximal biclique of a graph in this class is formed by those vertices that either are adjacent or dominate v, for some vertex v.

As a result, hereditary biclique-Helly graphs can have at most n maximal bicliques. The article is organized as follows. In the next section we introduce the notation and terminology employed. In Section 3 we develop a simple O(nm) time and O(n 2 ) space algorithm for the recognition of biclique-Helly graphs. Following, in Sections 4 and 5, we present an improved implementation of this simple algorithm, so that it runs in O(αm + n 2 ) time and O(n + m) space. The algorithm for enumerating the maximal bicliques of C 4 -dominated graphs with no triangles is described in Section 6. Finally, in Section 7, we give some remarks and leave some open problems. subscript from MAX, MIN, max, and min when there is no ambiguity. For two vertices v > w, define the least common neighborhood as L(v, w) = N (vw) ∩ MIN(v); note that, by definition, L(w, v) is undefined for v > w.

For W ⊆ V (G), denote by G[W ] the subgraph of G induced by W . An independent set is a set W ⊆ V (G) formed by pairwise non-adjacent vertices. Graph G is bipartite when V (G) can be partitioned into two independent sets W 1 and W 2 . In this case, the unordered pair {W 1 , W 2 } is called a bipartition of G. Furthermore, if vw is an edge of G for every v ∈ W 1 and w ∈ W 2 , then G is a complete bipartite graph. A biclique H of G is a complete bipartite induced subgraph of G with at least one edge; we also use the term biclique to refer to both V (H) and the unique bipartition of H.

Let F be a family of sets. Say that F is pairwise intersecting when S ∩ T = ∅, for every S, T ∈ F, while F is globally intersecting when F = ∅. Family F is Helly when all its pairwise intersecting subfamilies are globally intersecting. A graph G is biclique-Helly when its family of maximal bicliques is Helly, and it is hereditary biclique-Helly when all its induced subgraphs are biclique-Helly.

Denote by C n the cycle graph with n vertices; C 3 is also called a triangle. For a graph H, say that G is H-free when no induced subgraph of G is isomorphic to H. Similarly, for a family H of graphs, say that G is H-free when G is H-free for every H ∈ H. The arboricity α(G) of G is the minimum number of edge-disjoint spanning forests into which G can be decomposed. Chiba and Nishizeki proved that α(G) ≤ m 1/2 [START_REF] Chiba | Arboricity and subgraph listing algorithms[END_REF].

In this paper we also work with simple digraphs. Let D be a graph with vertex set V (D) and edge set E(D). Write v → D w to indicate that the ordered pair (v, w) is an edge of D. When (v, w) is not an edge of D, we write v

→ D w. For v ∈ V (D), define N + D (v) = {w ∈ V (D) | v → w} and N - D (v) = {w ∈ V (D) | w → v}. Sets N + D (v) and N - D (v)
are respectively the out-neighborhood and inneighborhood of v, while the members of N + D (v) and N - D (v) are the out-neighbors and in-neighbors of v, respectively. The out-degree and in-degree of v are the values

d + D (v) = |N + D (v)| and d - D (v) = |N - D (v)|, respectively.
When there is no ambiguity, we may omit the subscripts from →, →, N + , N -, d + , and d -.

Groshaus and Szwarcfiter proved the following characterization of hereditary biclique-Helly graphs, by means of minimal forbidden induced subgraphs.

Theorem 2.1 ([10])

A graph is hereditary biclique-Helly if and only if it is does not contain any triangles, C 5 's, C 6 's, nor ladders as induced subgraphs (see Figure 1).

As a consequence of this theorem, the authors obtain an O(n 3 m 2 ) time algorithm for the recognition of hereditary biclique-Helly graphs (cf. [START_REF] Mitre | Complexity aspects of the Helly property: graphs and hypergraphs[END_REF]).

Simple recognition of hereditary biclique-Helly graphs

In this section we rephrase Theorem 2.1 in such a way that an efficient recognition algorithm can be obtained. To describe our algorithm, we require the following definitions for a graph G. Say that a cycle of G is dominated if it contains a pair of dom-comparable vertices. When every C 4 of G is dominated, we say that G is C 4 -dominated. Theorem 2.1 is rephrased as follows.

Theorem 3.1 A graph is hereditary biclique-Helly if and only if it is C 4 -dominated and {triangle, C 5 , C 6 }-free.

Proof: By Theorem 2.1, graphs that contain triangles, C 5 's, or C 6 's as induced subgraphs are not hereditary biclique-Helly. Suppose now that G is a {triangle, C 5 , C 6 }-free graph that contains a cycle v 1 , v 2 , v 3 , v 4 in which neither v 1 and v 3 nor v 2 and v 4 are dom-comparable. For the sake of notation, call v i+4 = v i for every i ∈ Z. Then, for i ∈ Z, there is a vertex

w i ∈ N (v i ) \ N (v i+2 ). (Again, call w j+4 = w j for every j ∈ Z.) Since G is triangle-free, w i is adjacent to neither v i-1 nor v i+1 . Hence, w i = w j for every 1 ≤ i ≤ j = 4.
Clearly, v 1 , v 2 , v 3 , v 4 is an induced cycle because G is triangle-free. Now, consider all the possible edges between the vertices in {w 1 , w 2 , w 3 , w 4 }. First observe that w i is not adjacent to w i+2 ; otherwise

w i v i v i+1 v i+2 w i+2 would induce a C 5 in G. Similarly, w i is adjacent to neither w i-1 nor w i+1 ; oth- erwise w i-1 v i-1 v i-2 v i+1 w i+1 w i would induce a C 6 in G.
Therefore, the subgraph of G induced by {v i w i } 1≤i≤4 is isomorphic to a ladder and, by Theorem 2.1, G is not hereditary biclique-Helly .

For the converse, just observe that the cycle of a ladder formed by the vertices of degree at least 3 is not dominated. Then, the result follows from Theorem 2.1.

2

Theorem 3.1 yields an algorithm for the recognition of hereditary biclique-Helly graphs, summarized in Algorithm 1. For Step 1, the algorithm in [START_REF] Chiba | Arboricity and subgraph listing algorithms[END_REF] is called so as to find a triangle in O(mα(G)) time and O(n + m) space, when one exists. In the rest of this section we discuss a simple O(nm) time and O(m 2 ) space implementation for Steps 2 to 4. In the following sections we improve the implementation of this algorithm so as to run O(n 2 + α(G)m) time and linear space.

Algorithm 1 Recognition of hereditary biclique-Helly graphs. Input: a graph G. Output: if G is not hereditary biclique-Helly, then either a triangle, a non-dominated C 4 , an induced C 5 , or an induced C 6 ; otherwise, a message.

1. If G contains a triangle T , then output T and halt.

2.

If G contains a non-dominated C4 called C, then output C and halt.

3.

If G contains an induced C5 called C, then output C and halt.

4.

If G contains an induced C6 called C, then output C and halt.

5.

Output "G is HBH".

An O(nm) time implementation of Step 2

The main tools for this step are the squares families. Fix a degree ordered graph G with no triangles for the rest of this section.

For a vertex v, the squares family of v is the family S(v) that contains one triple S = (v, w, L(v, w)) for each w < v such that L(v, w) = ∅. Refer to v, w and L(v, w) as the high vertex, low vertex, and common neighborhood of S, respectively. When |L(v, w)| > 1, the triple S encodes all the C 4 's that contain v and w, where v is the maximum vertex of the C 4 . Indeed, v, a, w, b is a C 4 of G and v > max{a, b, w} if and only if a, b ∈ L(v, w). In this case, we say that S represents the cycle v, a, w, b, for every a, b ∈ L(v, w). The squares family of G is S(G) = v∈V (G) S(v). When G is understood, we will simply write S to mean S(G). Observe that every C 4 of G is represented by exactly one triple of S. Thus, the squares family of G encodes all the C 4 's of G in O(mα(G)) space, though G could have O(n 2 ) C 4 's [START_REF] Chiba | Arboricity and subgraph listing algorithms[END_REF]. For the sake of notation, write v(S), w(S), and L(S) to respectively mean the high vertex, the low vertex, and the common neighborhood of S, for every S ∈ S. Also, we sometimes write (v, w) instead of (v, w, L(v, w)); we may write, for instance, that (v, w) ∈ S to indicate that (v, w, L(v, w)) ∈ S.

Say that S ∈ S is dominated when all the C 4 's represented by S are dominated. (If |L(S)| = 1, then S is vacuously dominated.) By definition, G is C 4 -dominated if and only if S is dominated, for every S ∈ S. Say also that S is safe if v(S) dominates w(S), and that it is unsafe otherwise. Observe that if S is safe, then it is also dominated. Otherwise, S is dominated if and only if a dominates b, for every a, b ∈ L(S) such that a > b. These observations yield an algorithm to find a non-dominated C 4 of G, when one such C 4 exists, summarized as Algorithm 2.

Algorithm 2 Non-dominated C 4 of a triangle-free graph G. Input: a degree ordered graph G with no triangles. Output: if existing, a non-dominated C 4 of G; otherwise, a message.

1. Let v1 > . . . > vn be the vertices of G.

Compute the matrix

D ∈ {0, 1} n×n such that di,j = 1 if and only if vi dominates vj, for 1 ≤ i < j ≤ n. Write D(vi, vj) = di,j.
3. For i = 1 to n, do:

4.

Compute U N SAF E := {(vi, w, L(vi, w)) | L(vi, w) = ∅ and D(vi, w) = 0}.

5.

For each S ∈ U N SAF E do:

6.

Let a1 > . . . > a |L(S)| be the vertices of L(S)

7.

If D(aj, aj+1) = 0 for j ∈ {1, . . . , |L(S)| -1}, then output v(S), aj, w(S), aj+1 and halt.

8.

Output "G is C4-dominated".

In Step 4, Algorithm 2 finds each unsafe S ∈ S(v i ). Following, the inner cycle checks that every such unsafe triple S is dominated. For this, it first computes a degree ordering a 1 > . . . > a |L(S)| of L(S), and then checks that a j dominates a j+1 , for every 1 ≤ j < |L(S)|. If this check is fulfilled, then, since domination is a transitive relation, we obtain that a dominates b for every a, b ∈ L(S) such that a > b. Thus, Algorithm 2 is correct. Algorithm 2 can be implemented so as to run in O(nm) time and O(n 2 ) space. A better implementation is given in Section 4.

An O(nm) time implementation of Steps 3 and 4

For this paragraph, suppose that G is a degree ordered graph that is C 4 -dominated and contains no triangles. The next lemma shows how to find an induced C 6 in G that contains any given vertex v ∈ V (G), if existing. We omit its proof because a stronger version appears in Section 5. Lemma 3.2 Let G be a degree ordered graph that is C 4 -dominated and contains no triangles, and v 0 ∈ V (G). Then, there is an induced C 6 in G that contains v 0 if and only if there is a cycle v 0 , . . . , v 5 with the following properties:

(i) v 3 ∈ N (v 0 ), (ii) v 1 = min N (v 0 v 2 ) and v 5 = min N (v 0 v 4 ), (iii) v 0 is dominated by neither v 2 nor v 4 ,

and

(iv) v 1 and v 5 are not dom-comparable.

The above lemma yields Algorithm 3, that finds an induced C 6 in O(nm) time and O(n 2 ) space, if existing. A similar algorithm can be used to find if there is an induced C 5 . Just observe that there is an induced C 5 containing a vertex v if and only if there are two adjacent vertices w and z at distance 2 from v. In Section 5 we devise better algorithms for finding if there is an induced C 5 or C 6 .

Algorithm 3 Induced C 6 in a C 4 -dominated graph G with no triangles. Input: a degree ordered graph G that is C 4 -dominated and contains no triangles. Output: if existing, an induced C 6 of G; otherwise, a message.

1. Let v1 > . . . > vn be the vertices of G.

Compute the matrix

D ∈ {0, 1} n×n such that di,j = 1 if and only if vi dominates vj, for 1 ≤ i < j ≤ n. Write D(vi, vj) = di,j.

3.

For each w0 ∈ V (G), do:

4. Compute N2 := {w2 ∈ V (G) | N (w0w2) = ∅ and D(w2, w0) = 0}

5.

For each w2 ∈ N2, set p(w2) := min N (w0w2).

6.

If there is a vertex w3 ∈ N (w0) that is adjacent to w2, w4 ∈ N2 and D(p(w2), p(w4)) + D(p(w4), p(w2)) = 0, then output w0, p(w2), w2, w3, w4, p(w4) and halt.

7.

Output "G contains no induced C6's".

Faster recognition of C -dominated graphs with no triangles

In this section we develop an improved implementation of Algorithm 2 whose running time and space consumption are O(mα(G)) and O(n + m), respectively. The idea is the same, for each S ∈ S we first check if S is safe. If not, then we check the dominations between the vertices in L(S). The major difference is that the domination matrix D is no longer employed; instead, while checking the safeness, we compute a digraph that encodes some dominations of interest of G. We begin with the description of this digraph. As before, we assume that G is a degree ordered graph with no triangles. Fix S ∈ S. Define the binary relation → S on L(S) as follows: for a, b ∈ L(S), a → S b if and only if a < b and there is no c ∈ L(S) such that a < c < b. In other words, → S defines the subordering of < induced by the members in L(S). We require a generalization of S from vertices to sets. For V ⊆ V (G), define S(V ) = v∈V S(v). Note that S(∅) = ∅ and S(V (G)) = S(G). Now we are ready to define the domination digraph.

v 2 v 8 v 5 v 7 v 3 v 1 v 9 v 6 v 10 v 4
Fig. 2: An ordered graph G where vi < vj if and only if i < j

For V ⊆ V (G), the unsafe domination digraph of V is the digraph U (V ) with vertex set V (G) such that, for a, b ∈ V (G), a → D b if and only if a → S b
for some unsafe S ∈ S(V ). In other words, for each unsafe S ∈ S(V ), there is a path that goes through the vertices of L(S) in the order given by <. The

unsafe domination digraph of G is the digraph U (G) = U (V (G)).
For an example, consider the ordered graph G depicted in Figure 2, where v i < v j if and only if i < j, and let S = (v 10 , v 5 ) and T = (v 9 , v 5 ). By definition,

v 6 → S v 8 and v 6 → T v 7 because L(v 10 , v 5 ) = {v 7 , v 6 } and L(v 9 , v 5 ) = {v 8 , v 6 }. Hence, v 6 → v 7 is an edge of U ({v 10 }), while v 6 → v 8
is an edge of U ({v 10 , v 9 }). These two edges are the only edges of

U (G) = U (V (G)), because L(v i , v j )
is either empty or a singleton for any i ≤ 8.

The following lemma shows that, when every S ∈ S(V ) is dominated, U (V ) is actually a directed forest that encodes some dominations. Lemma 4.1 Let G be a degree ordered graph that is C 4 -dominated and contains no triangles, and V ⊆ V (G). If S dominated for every S ∈ S(V ), then the following conditions hold for any v ∈ V (G):

(i) d + U (V ) (v) ≤ 1, and (
in G. Also, since v → T b, it follows that v < b, i.e. d G (b) ≥ d G (v), hence b is neither dominated by v in G. But then, T ∈ S(V ) is not dominated. (ii). If d + U (V ) (v) = 0, then (
ii) is vacuously true. Otherwise, let w be an out-neighbor of v. Since v → U (V ) w, we obtain that v → S w, for some unsafe S ∈ S(V ). Since S is dominated and unsafe, it follows that w dominates v in G.

2

Recall that the idea of the new implementation is to build U (G) so as to test the dominations inside L(S), for every unsafe S ∈ S. In turn, to build U (G), we need to know the safeness status of some triples in S, for which we require the dominations of these triples. It turns out that U (G) can be iteratively computed while the partial results are used to check the safeness of those triples of interest. The next lemma shows how this construction is done. Proof: (i) =⇒ (ii). Suppose first that S is safe, i.e., v dominates w. By definition, L = N (vw)∩MIN(v), thus |L| = |N (w) ∩ MIN(v)|. Now, suppose that there is some unsafe T ∈ S(MAX(v)) such that w ∈ L(T ). In this case, since v dominates w, it follows that v is adjacent to both v(T ) and w(T ). Hence v ∈ L(T ), because v < v(T ) as T ∈ S(MAX(v)). Therefore, there is a path from w to v in U (MAX(v)) because v > w.

(ii) =⇒ (i). In this case, we argue by contradiction. Suppose that (ii) is true and yet S is unsafe, i.e., N (w)\N (v) contains some vertex z.

Since L = N (vw)∩MIN(v) ⊆ N (v) and |L| = |N (w)∩MIN(v)|, we obtain that L = N (w) ∩ MIN(v), thus z > v. Fix a ∈ L.
Since w is adjacent to both z and a, it follows that w ∈ L(z, a), thus (z, a) ∈ S(z). Also, since v ∈ N (a)\N (z), it follows that (z, a) is unsafe, so there is a path from w to v in U (MAX(v)). Therefore, by Lemma 4.1, v dominates w, a contradiction. 2 Lemma 4.2 yields Algorithm 4. Its input is the graph G, and its output is

U (G) if G is C 4 -dominated,
or a non-dominating cycle otherwise. Thus, Algorithm 4 is just a replacement of Algorithm 2. We discuss its correctness and complexity in the next paragraphs. 3. For i := 1, . . . , n, do:

4.

Set REACH := {w ∈ V (G) | d < (w) > 0 and there is a path from w to vi in U }.

5.

For each S ∈ {(vi, w, L) ∈ S | either |L| = d < (w) or (w ∈ U N SAF E and w ∈ REACH)}.

{This loop checks that every unsafe S is dominated.}

6.

For each a, b ∈ L(S) such that a →S b do:

7.

If N + U (a) ⊂ {b}, then output vi, a, w(S), b and halt.

8.

If N + U (a) = ∅ and a is not dominated by b, then output vi, a, w(S), b and halt. 9.

Add a → b to U .

10.

Set U N SAF E := U N SAF E ∪ L(S).

11.

Set d < (w) := d < (w) -1, for every w ∈ N (vi).

12. Output U .

Correctness of Algorithm 4

The Loop 3-11 examines the vertices in the order defined by <, beginning from the greatest. Fix i ∈ {1, . . . , n}, and call M AX = MAX(v i ), and M IN = MIN(v i ). Observe that, by Step 1, M AX = {v 1 , . . . , v i-1 }, and M IN = {v i+1 , . . . , v n }. Immediately before Loop 3-11 is executed for v i , every S ∈ S(M AX) is dominated, and the state of the variables is as follows:

(i) U N SAF E = {v ∈ V (G) | v ∈ L(S)
for some unsafe S ∈ S(M AX)}.

(ii) U = U (M AX). (iii) d < (v) = |N (v) ∩ (M IN ∪ {v i })|, for every v ∈ V (G).
Step 4 finds all those w ∈ V (G) such that there is a path from w to v i in U (M AX), and d < (w) > 0. Observe that if d < (w) = 0, then, by (iii), L(v i , w) = ∅, thus (v i , w) ∈ S. Then, by Lemma 4.2, Loop 5-10 iterates every unsafe triple S ∈ S whose high vertex is v i . This loop is the responsible for testing whether S is dominated or not, and it has the following three alternatives. Alternative 2: the algorithm halts at Step 8 while examining a → S b. This alternative occurs when a is not dominated by b, thus S is not dominated. Therefore, G is not C 4 -dominated.

Alternative 3: the algorithm does not halt inside Loop 5-10. In this last alternative, for every a → S b, either N + U (a) = {b} or a is dominated by b. Whichever the case, by (ii), a is dominated by b and a → b is an edge of U (M AX ∪ {v}). In particular, S is dominated. Therefore, if Loop 5-10 halts if and only if S(M AX ∪ {v i }) contains a non-dominated triple. Furthermore, if Loop 5-10 does not halt, then by Step 9, (ii) is satisfied before the execution of the outer loop for v i+1 . Finally, by Steps 10 and 11, (i) and (iii) also hold immediately before the execution of Loop 3-11 for v i+1 . (Observe that Step 7 is superfluous, and it can be removed from the algorithm without affecting its correctness. However, its inclusion drops the time complexity required by the algorithm. In some sense, it tells us that the domination of a by b was already tested.) Algorithm 4 gives its output in one of three steps. Suppose that the algorithm halts at Step 7, as in Alternative 1. This happens because there is an unsafe triple T , already processed by the algorithm, such that a → T µ(a). We claim that b < µ(a); otherwise, as in Lemma 4.1, T would not be dominated, contradicting the fact that Algorithm 4 stops immediately after it process a non-dominated triple. Then, as in Lemma 4.1, a is not dominated by b. Similarly, if Algorithm 4 halts at Step 8, as in Alternative 2, then a is not dominated by b. Therefore, in both of these alternatives, v i , a, w(S), b is a non-dominated C 4 . Finally, if Algorithm 4 does not halt inside Loop 5-10, as in Alternative 3, then U = U (G), by (ii). Summing up, Algorithm 4 is correct.

Implementation and complexity of Algorithm 4

The implementation of Algorithm 4 is rather straightforward. Recall that, by Lemma 4.1, every vertex of U has at most one out-neighbor. We record such out-neighbors in a vector with n positions, where the i-th

position is b if and only if v i → U b. If N + (v i ) = ∅,
then the i-th position of the array is some undefined value ⊥. Similarly, d < and U N SAF E are also stored in vectors with n positions; the i-th position respectively indicates the values of d < (v i ) and v i ∈ U N SAF E. We assume that a can be inserted into N - U (b) in O(1) time at Step 9, and that a can be also removed from N - U (b) in O(1) time when d < (a) drops from 1 to 0 at Step 11. This can be achieved by storing N - U (b), for every b ∈ V (G), and a pointer from a to its position in N - U (b), for every a ∈ N - U (b). The time complexity of the algorithm with the above implementation is as follows. Fix i ∈ {1, . . . , n}. Before entering the Loop 3-11 for v i , S(v i ) is obtained by executing one iteration of method C4 developed by Chiba and Nishizeki in [START_REF] Chiba | Arboricity and subgraph listing algorithms[END_REF]. Such iteration takes G and a vertex v i ∈ V (G) as input, and it outputs S(v i ). (In fact, method C4 discards those S ∈ S(v i ) for which |L(S)| = 1. However, the algorithm can be easily modified so as to output these triples as well.) Furthermore, for each S ∈ S(v i ), the obtained list L(S) is ordered in such a way that a ∈ L(S) appears before b ∈ L(S) if and only if a > b, i.e., b → S a if and only if a immediately precedes b. As proved in [START_REF] Chiba | Arboricity and subgraph listing algorithms[END_REF]

O   n + v∈V (G) S∈S(v) |L(S)|   = O(n + mα(G)).
On the other hand, only

O   n + max v∈V (G)    S∈S(v) |L(S)|      = O(n + m)
bits of additional space are used by the algorithm, thus the space complexity is O(n + m).

Faster recognition of hereditary biclique-Helly graphs

In this section we improve Algorithm 3, and the corresponding algorithm that finds an induced C 5 , so that both run in O(mα(G) + n 2 ) time and O(n + m) space. Again, the idea is to evaluate if a given vertex v belongs to an induced C 5 or an induced C 6 , by looking at those vertices at distance at most 3 from v. In this section, however, we take advantage of the dominations implied by the squares family of G. The improved algorithm that finds an induced C 5 is rather similar to the improvement of Algorithm 3 for finding an induced C 6 . So, we only describe in detail the improvement of Algorithm 3. The main tool in this section is a new forest that extends the unsafe domination digraph. For the rest of this section, suppose that G is a degree ordered graph that is C 4 -dominated and has no triangles.

The squares domination digraph of G is the digraph S(G) that is obtained from U (G) by inserting an edge w → v for every safe (v, w) ∈ S.

Fix v ∈ V (G). Define σ(v) = min N + S(G) (v), when d + S(G) (v) > 0. We write σ(v) = ⊥ to indicate that d + S(G) (v) = 0.
For the sake of simplicity, we assume

⊥ > max V (G).
The following lemma is analogous to Lemma 3.2. It shows how to find an induced C 6 , when one such cycle exists. Observe the role that σ plays by marking that v 2 and v 4 are not dom-comparable (condition (ii)), and that v 1 , v 3 , and v 5 are neither dom-comparable (condition (iii)). Indeed, σ(v i ) was chosen as the minimum that dominates v i in either U (G) or in a safe triple. So, if v < σ(w), and v and w share a C 4 , then v cannot dominate w. Lemma 5.1 Let G be a degree ordered graph that is C 4 -dominated and contains no triangles. Then, G contains an induced C 6 if and only if it contains two paths v 0 , v 1 , v 2 , v 3 and v 0 , v 5 , v 4 , v 3 such that

(i) v 2 = v 4 , v 3 ∈ N (v 0 ) and v 0 > max{v 1 , v 2 , v 4 , v 5 }, (ii) σ(v 2 ) > v 0 and σ(v 4 ) > v 0 , and (iii) σ(v 1 ) = σ(v 3 ) = σ(v 5 ). Furthermore, if G contains the paths v 0 , v 1 , v 2 , v 3 and v 0 , v 5 , v 4 , v 3 satisfying (i)-(iii), then v 0 , . . . , v 5 induce a cycle in G.
Proof: Suppose first that G contains an induced C 6 . For each vertex v, define r(v) as the number of vertices reached from v in S(G). For each

C ⊆ V (G), define R(C) = v∈C r(v).
From among all the induced C 6 's of G, chose the cycle v 0 , . . . , v 5 such that:

(1) there is no induced C 6 of G containing a vertex in MAX(v 0 ), and

(2) R({v 0 , . . . , v 5 }) is minimum among those cycles containing v 0 .

We claim that paths

v 0 , v 1 , v 2 , v 3 and v 0 , v 5 , v 4 , v 3 satisfy (i)-(iii). Clearly, v 2 = v 4 , v 3 ∈ N (v 0 )
, and v 0 > max{v 1 , . . . , v 5 }, thus (i) follows. Suppose, contrary to statement (ii), that σ(v 2 ) ≤ v 0 . Notice that v 2 is not dominated by v 0 , so σ(v 2 ) < v 0 . Then, σ(v 2 ) = ⊥, hence σ(v 2 ) dominates v 2 . By (2), v 0 , v 1 , σ(v 2 ), v 3 , v 4 , v 5 do not induce a cycle in G, because r(v 2 ) > r(σ(v 2 )). Thus, as G is triangle-free, we obtain that σ(v 2 ) is adjacent to v 1 , v 3 , and v 5 , hence, v 0 , v 1 , σ(v 2 ), v 5 is a C 4 . Now, since G is C 4 -dominated and v 1 and v 5 are not dom-comparable, it follows that σ(v 2 ) dominates v 0 . However, this contradicts the fact that σ(v 2 ) < v 0 . Similar arguments prove that σ(v 4 ) > v 0 , so (ii) follows.

Finally, consider statement (iii). Clearly, (iii) is true when σ(v 1 ) = σ(v 3 ) = σ(v 5 ) = ⊥. Suppose, then, that σ(v i ) = ⊥, for some i ∈ {1, 3, 5}. In this case, σ(v i ) dominates v i , by definition of σ. Again, by [START_REF] Vânia | Generating bicliques of a graph in lexicographic order[END_REF], we obtain that σ(v i ) must be adjacent to v 0 , v 2 , and v 4 , or otherwise v i could be replaced by σ(v i ) so as to obtain an induced C 6 with lower value of R.

Then, {v 0 , v 1 , v 2 , σ(v i )}, {v 0 , v 5 , v 4 , σ(v i )}, and {v 2 , v 3 , v 4 , σ(v i )} all induce C 4 's. Since G is C 4 -dominated and v 0 , v 2 , v 4 are pairwise not dom- comparable, it follows that σ(v i ) dominates v 1 , v 3 ,
and v 5 . Thus, none of σ(v 1 ), σ(v 3 ), and σ(v 5 ) is equal to ⊥. Repeating the above arguments for i = 1, 3, and 5, we obtain that σ(v i ) dominates v j for every i, j ∈ {1, 3, 5}. Then (iii) follows, because σ(v) = min N + S(G) (v), for every v ∈ V (G). For the converse, suppose that there are two paths v 0 , v 1 , v 2 , v 3 , and v 0 , v 5 , v 4 , v 3 that satisfy (i)-(iii). Observe that it is enough to prove that v 1 ∈ N (v 4 ) and v 5 ∈ N (v 2 ). Indeed, in this case v 1 = v 5 , thus v 0 , . . . , v 5 is a cycle of G and, as G is triangle-free, this cycle is induced.

Suppose, to obtain a contradiction, that

v 1 ∈ N (v 4 ). Then, v 1 , v 2 , v 3 , v 4 is a C 4 in G.
This cycle is represented by some S ∈ S. Consider the following cases.

Case 1: v(S) ∈ {v 2 , v 4 }. Observe that w(S) ∈ {v 2 , v 4 }, so σ(w(S)) > v 0 > v(S) by (i) and (ii). Then, v(s) does not dominate w(S), thus S is an unsafe triple of S. Consequently, since v 1 , v 3 ∈ L(S) and v 0 ∈ N (v 1 ) \ N (v 3 ), it follows that v 1 dominates v 3 , thus there is a path from

v 3 to v 1 in U (G). Then, σ(v 1 ) > v 1 ≥ σ(v 3 ), a contradiction.
Case 2: v(S) ∈ {v 2 , v 4 }. In this case, both v 2 , v 4 belong to L(S), thus, as σ(v 2 ) > v 0 > v 4 and σ(v 4 ) > v 0 > v 2 , we obtain that S must be safe. Consequently, since

v 0 ∈ N (v 1 ) \ N (v 3 ), it follows that S = (v 1 , v 3 ). This is again impossible, because σ(v 1 ) > v 1 ≥ σ(v 3 ).
Replacing v 1 by v 5 above, we obtain that v 5 ∈ N (v 2 ) as well. Thus, v 0 , . . . , v 5 is an induced cycle of G. 2

Lemma 5.1 implies Algorithm 5. Its input is the graph G, and its output is a message if G contains no induced C 6 , or an induced C 6 otherwise. Thus, Algorithm 5 is just a replacement of Algorithm 3. We discuss the algorithm, its correctness, and its complexity in the next paragraphs.

Algorithm 5 Induced C 6 of a triangle-free C 4 -dominated graph. Input: a degree ordered graph G that is C 4 -dominated and has no triangles. Output: if existing, an induced C 6 of G; otherwise, a message.

1. Let v1 > . . . > vn be the vertices of G.

2. Compute σ(v), for every v ∈ V (G). 3. For each vw ∈ E(G), set X(v, w) := {z ∈ N (v) | σ(z) = w} and X(w, v) := {z ∈ N (w) | σ(z) = v}.

4.

For i := 1 to n, do:

5.

Set N1 := {w1 ∈ N (vi) | w1 < vi}.

6.

Set N2 := w 1 ∈N 1 {w2 ∈ N (w1) | σ(w2) > vi > w2}.

7.

For each w2 ∈ N2, set N3(w2) := {X(w2, σ(w1)) \ N1 | w1 ∈ N1 ∩ N (w2)}.

8.

For w2, w4 ∈ N2 (w2 = w4), if N3(w2) ∩ N3(w4) contains a vertex, say w3, then:

9.

Output vi, w1, w2, w3, w4, w5, for some w1, w5 ∈ N1 such that w1 = w5 and σ(w1) = σ(w5) = σ(w3), and halt.

10.

Output "G contains no induced C6's."

Correctness of Algorithm 5

Algorithm 5 either halts at Step 9 or it runs until its termination. In this paragraph, we prove that Algorithm 5 halts at Step 9 if and only if G contains an induced C 6 . Furthermore, when Algorithm 5 halts at

Step 9, its output is an induced C 6 of G. Suppose first that Algorithm 5 halts at Step 9, when the i-th iteration of Loop 4-9 is being executed. Examine the state of the variables immediately before Step 9 is executed. By Steps 3, 5 and 7, w 3 ∈ N (w 2 w 4 ) \ N (v i ), and there are two vertices w 1 ∈ N (v i w 2 ) and w 5 ∈ N (v i w 4 ) such that σ(w 1 ) = σ(w 3 ) = σ(w 5 ). By Steps 5 and 6, v i > max{w 1 , w 2 , w 4 , w 5 }, so, by Lemma 5.1, v i , w 1 , . . . , w 5 induce a C 6 in G.

that testing membership in N 1 and N 2 takes O(1) time, while X(w 2 , σ(w 1 )) can be obtained in O(1) time while examining w 2 in a traversal of N (w 1 ) with the pointer x(w 1 , w 2 ) (notice that w 1 ∈ X(w 2 , σ(w 1 )) by definition, so x(w 1 , w 2 ) was previously recorded). As each vertex outside N 1 is marked at most twice, the time required by Steps 7 and 8 is O(n + w1∈N1 d(w 1 )). Finally, if the condition at Step 8 is true, then we obtain a vertex w 3 that has two marks, say (w 1 , w 2 ) and (w 5 , w 4 ). These marks indicate that w 3 ∈ X(w 2 , σ(w 1 )) ∩ X(w 4 , σ(w 5 )), this v i , w 1 , . . . , w 5 is a valid output for Step 9. Clearly, this step takes O(1) time. Summing up, by [START_REF] Chiba | Arboricity and subgraph listing algorithms[END_REF], Algorithm 5 has time complexity

O α(G)m + n i=1 {d(w) + n | w ∈ N (v i ) ∩ MIN(v i )} = O(n 2 + α(G)m).
As for the space complexity, recall again that w belongs only to X(v, σ(w)), for every edge vw. Therefore, as each call to method C4 takes O(n + m) space, Algorithm 5 requires O(n + m) bits.

Finding an induced C 5 efficiently

An induced C 5 can be found in O(n 2 + mα(G)) time and linear space, if existing, with a procedure similar to Algorithm 5. We omit the implementation details, that follow from the next lemma. Lemma 5.2 Let G be a degree ordered graph that is C 4 -dominated and contains no triangles. Then G contains an induced C 5 if and only if it contains a cycle v 0 , . . . , v 4 such that min{σ(v 2 ),

σ(v 3 )} > v 0 > max{v 2 , v 3 }.
The main theorem of this paper is the following corollary.

Maximal bicliques of C 4 -dominated graphs with no triangles

In this section we focus on the problem of enumerating all the maximal bicliques of a C 4 -dominated graph with no triangles. At the end of this section, we also devote a paragraph to discuss some biclique problems on this class of graphs.

Observe that every pair of twin vertices of any graph G belong to the same maximal bicliques. Thus, every maximal set of twin vertices S can be identified into one vertex v(S) so as to obtain a twin-free graph H. Then, for every maximal biclique B of H, we can replace each v(S) ∈ B with the set S so as to obtain a maximal biclique of G. So, in this section we assume that G is a degree ordered graph that is C 4 -dominated and has no triangles nor twins.

For

each v ∈ V (G), define B(v) = {N (v), Dom(v) ∪ {v}}. Observe that, since G is triangle-free, B(v) is a biclique of G.
The following theorem shows that {B(v) | v ∈ V (G)} is precisely the family of maximal bicliques of G. Theorem 6.1 Let G be a degree ordered graph that is C 4 -dominated and has no triangles nor twins, and B be a biclique of G. Then, B is a maximal biclique of G if and only if B = B(v) for some v ∈ V (G).

Proof: Suppose first that B is a maximal biclique of G, and let {B 1 , B 2 } be its bipartition. Fix v 1 = min B 1 and v 2 = min B 2 . To obtain a contradiction, suppose that neither B 1 ⊆ Dom(v 1 ) nor B 2 ⊆ L(S) = {w} for every S ∈ S, thus the dominator set of w is N (z) \ {w}. Hence, v belongs to the dominator set of w.

For the converse, suppose that v belongs to the dominator set of w, and call z = min N (w). By definition, v ∈ N (z). Note that, if N (w) = {z}, then w is dominated v. Suppose then that d(w) > 1, and take a ∈ N (w) \ {z}. Since N (w) ⊆ MAX(w), we obtain that a > z > w, thus (a, z) ∈ S. Also, L(a, z) = {w}, because otherwise the dominator set of w would be empty, and this cannot happen as it contains v. Furthermore, since w has no out-neighbors in S(G) and |L(a, z)| > 1, it follows that (a, z) is a safe triple of S. Therefore, a dominates z, hence a is adjacent to v. Since a is any vertex in N (w) \ {z}, it follows that v is adjacent to all the vertices in N (w), hence v dominates w.

2

The domination digraph of G is the digraph D(G) that is obtained from S(G) by inserting an edge w → v, for every degenerated w ∈ V (G) and every v in the dominator set of w. As its name indicates, D(G) encodes all the dominations in G, as the following theorem resumes. Theorem 6.5 Let G be a degree ordered graph that is C 4 -dominated and has no triangles nor twins, and v, w ∈ V (G). Then, v dominates w in G if and only if there is a path from w to v in D(G). Furthermore, if v dominates w and w → D(G) v, then there is a path from w to v in U (G).

Proof: Suppose that w is dominated by v. If w is degenerated, then w → v is an edge of D(G), by Lemma 6.4. Otherwise, either w has a neighbor in MIN(w) or w has an out-neighbor in S(G). Consider these alternatives:

Alternative 1: w is adjacent to z ∈ MIN(w). In this case, z ∈ L(v, w), thus (v, w) is a safe triple of S.

Therefore, v is an out-neighbor of w in both S(G) and D(G).

Alternative 2: N (w) ⊆ MAX(w) and d + U (G) (w) = 0. In this case, w has an out-neighbor z in S(G) such that (z, w) is a safe triple of S. Then, as v dominates w, it follows that v is adjacent to all the vertices in L(z, w). Therefore, L(v, w) = ∅, thus (v, w) is a safe triple of S. Consequently, w → v is an edge of both S(G) and D(G).

Alternative 3: w has an out-neighbor in U (G), say z. For this to happen, there must be an unsafe triple S ∈ S such that L(S) contains both w and z. If v(S) > v, then L(S) contains also v, and so there is a path from w to v in both U (G) and D(G). Otherwise, v(S) < v and, since v dominates w, it follows that v(S) ∈ L(v, w). Hence, (v, w) is a safe triple of S, and w → v is an edge of both S(G) and D(G).

The converse follows from Lemmas 4.1 and 6.4 and the definition of D(G), while alternatives above are enough to conclude that there is a path from w to v in U (G) for every v, w such that v dominates w and w → D(G) v. 2 Corollary 6.6 Let G be a degree ordered graph that is C 4 -dominated and has no triangles nor twins. For every v ∈ V (G), Dom(v) is equal to the set of ancestors of v in D(G).

The above corollary can be used to improve the algorithm for listing the maximal bicliques, as it is shown in Algorithm 6. The correctness of Algorithm 6 follows from Lemmas 6.3 and 6.4 and Corollary 6.6. With respect to its implementation, the domination matrix is represented simply with successors and predecessors lists, d(v) and dom(v) are stored together with v, and R is stored in an vertex with n positions, so that each membership query takes O(1) time.

as in Algorithm 6, |Dom(v)| is either the level of v in U (G) plus the number of safe triples (w, v) ∈ S with v → U (G) w (when v is not degenerate) or the number of vertices in its dominator set (when v is degenerate). (Twin vertices are ignored by Theorems 6.1 and 6. andc) maximum edge biclique problem, and are all NP-complete for general graphs [START_REF] Garey | A guide to the theory of NP-completeness[END_REF][START_REF] Peeters | The maximum edge biclique problem is NP-complete[END_REF]. Furthermore, problem c) is NP-complete even when G is a bipartite graph [START_REF] Peeters | The maximum edge biclique problem is NP-complete[END_REF].

Concluding remarks and open problems

In this paper we devised an efficient algorithm for the recognition of hereditary biclique-Helly graphs. In this section we leave some questions whose answers could imply a better algorithm.

In Section 5, we showed how to find an induced C 6 in a C 4 -dominated graph with no triangles. As part of Algorithm 5, we had to find some vertices that appear at distance at most 3 from a given vertex v. We showed how to do this in O(n) time, by traversing each vertex outside N (v) at most twice. However, not all the vertices outside N (v) are at distance 3 from G, unless G is somehow dense. An open question that follows is, then, can an induced C 6 be found in O(α(G)m) time? Furthermore, is it possible to do find such C 6 by using only O(n + m) space?

In Section 6, we develop an algorithm for enumerating the bicliques in O The somehow opposite question is also interesting. Instead of implicitly storing each domination of the first class as a path, we can store it explicitly. That is, we can insert an edge w → v into D(G) for every path of U (G) beginning at w and ending at v. Such digraph would require O(o) space. We know that o < n 2 ; however, for w to be dominated by a vertex at distance k from v in D(G), there should be at least k vertices in N (w) \ N (v) (always assuming that G is twin-free). Thus if D(G) has many large paths, then G is dense and α(G) is large. So, it would be nice to prove or disprove that o ∈ O(α(G)m), or that o ∈ O(m 3/2 ).

Let B be the class of graph formed by those graphs G such that {B(v)} v∈V (G) is the family of maximal bicliques of G. By Theorem 6.1, every C 4 -dominated graph with no triangles belongs to B. The converse is false, since the graph in Figure 3 belongs to B and it contains a non-dominated C 4 . The graphs in B have at most n bicliques, and Lemma 6.3 holds for all the graphs in B. Hence, the simple algorithm that lists {B(v)} v∈V (G) by using the domination matrix, implies that the maximal bicliques of the graphs in B can be enumerated in O(nm) time and O(n 2 ) space. Is it possible to list the maximal bicliques of the graphs in B faster? Is it possible obtain the same time and space bounds of Algorithm 6 for a larger class of graphs? Fig. 3: A graph G that contains a non-dominated C4, whose family of maximal bicliques is {B(v)} v∈V (G) .

Fig. 1 :

 1 Fig. 1: The ladder graphs.

  ii) v is dominated in G by all its out-neighbors.Proof: (i). Suppose that v ∈ V (G) has at least two out-neighbors a > b in U (V ). Then, by definition, there are two unsafe triples in S(V ), say S and T , such that v ∈ L(S) ∩ L(T ), v → S a, and v → T b. Now, since a > b and v → S a, it follows that b < v(S) and b ∈ L(S). Consequently, b is not adjacent to either v(S) or w(S), thus v is not dominated by b

Lemma 4 . 2

 42 Let G be a degree ordered graph that is C 4 -dominated and contains no triangles, and S ∈ S. Call v = v(S), w = w(S), and L = L(S). If every triple of S(MAX(v)) is dominated, then the following are equivalent statements.(i) S is safe.(ii) |L| = |N (w) ∩ MIN(v)| and if w ∈ L(T ) for some unsafe T ∈ S(MAX(v)), then there is a path from w to v in U (MAX(v)).

Algorithm 4 1 . 2 .

 412 Non-dominated C 4 of a triangle-free graph G. Input: a degree ordered graph G with no triangles. Output: if G is C 4 -dominated, then U (G); otherwise, a non-dominated C 4 of G. Let v1 > . . . > vn be the vertices of G. Set U N SAF E := ∅, U := (V (G), ∅) and d < (v) := |N (v)|, for every v ∈ V (G).

Alternative 1 :

 1 the algorithm halts at Step 7 while examining a → S b. For this to happen, N + U (a) must contain a vertex different than b, say µ(a). Thus, by (ii), both b and µ(a) are out-neighbors of a in U (M AX ∪ {v i }). Therefore, G is not C 4 -dominated by Lemma 4.1.

  , this iteration of C4 costs O( S∈S(vi) |L(S)|) time. For Step 4, just use a tree traversal algorithm, taking advantage that N - U (b) is stored for every b ∈ V (G). Such a traversal takes O(1) time per vertex traversed. Observe that w is traversed at Step 4 if and only if L(v i , w) = ∅, thus Step 4 takes O(|S(v i )|) time. Finally, Loop 5-10 takes O(|L(S)|) time to examine each S ∈ S(v i ). Thus, this loop also requires O( S∈S(vi) |L(S)|). Finally, all the steps outside the Loop 3-11 cost O(n) time. Therefore, as proven in [1], the time complexity of Algorithm 4 is

Theorem 5 . 3

 53 Hereditary biclique-Helly graphs can be recognized in O(n 2 +α(G)m) time and O(n+m) space.

  5; nevertheless, they can be counted as well when |Dom(v)| is being computed.) Therefore, for k ∈ N, we can test, in O(α(G)m) time and O(n + m) space, whether G has a biclique (B 1 , B 2 ) such that: a) |B 1 | = |B 2 | = k, b) |B 1 | + |B 2 | ≥ k, or |B 1 | • |B 2 | ≥ k. These problems are respectively called: a) balanced biclique problem, b) maximum vertex biclique problem,

  (o + α(G)m) time and O(α(G)m) space. Algorithm 6 uses the domination digraph D(G) that encodes all the dominations in O(α(G)m) space. We can divide the dominations encoded in D(G) into three classes. Those corresponding to paths in U (G); those corresponding to edges in S(G) -U (G); and those corresponding to edges in D(G) -S(G). Although there can be as many as O( v∈V (G) Dom(v)) = O(o) dominations of the first class, only O(n) space is used by D(G) to encode this information. On the other hand, Proposition 6.7 guaranties that there are only O(m) dominations of the third class. Finally, O(α(G)m) bits are used to store the O(α(G)m) dominations second class. Could it be possible to encode such dominations in a different way (e.g. as paths), so that only O(n + m) space is used, without affecting the time complexity of the algorithm?

Grant 20020100300048, PICT ANPCyT Grant 1970, and CONICET PIP Grant 11220100100310 1365-8050 c 2013 Discrete Mathematics and

For the converse, suppose that G contains an induced C 6 . By Lemma 5.1, there must be two paths w 0 , w 1 , w 2 , w 3 and w 0 , w 5 , w 4 , w 3 satisfying conditions (i)-(iii) of the lemma. Vertex w 0 gets some name v i in Algorithm 5, for some 1 ≤ i ≤ n. If Algorithm 5.1 halts before the i-th iteration of Loop 4-9, then there is nothing to prove. So, suppose that the i-th iteration of Loop 4-9 is executed, and consider its effects. By Step 5 and Lemma 5.1 (i), w 1 , w 5 ∈ N 1 . By Step 6 and Lemma 5.1 (i)-(ii), w 2 , w 4 ∈ N 2 . By Step 3 and Lemma 5.1 (iii), w 3 belongs to both X(w 2 , σ(w 1 )) and X(w 4 , σ(w 5 )), thus, by Step 7 and Lemma 5.1 (i), w 3 ∈ N 3 (w 2 ) ∩ N 3 (w 4 ). Therefore, the condition of Step 8 is satisfied, and Algorithm 5 halts at Step 9. Finally, observe that Step 9 always finds the vertices w 1 = w 5 such that σ(w 1 ) = σ(w 5 ) = σ(w 3 ). Indeed, such w 1 and w 5 exist as argued before. And, by Lemma 5.1, v i , w 1 , . . . , w 5 induce C 6 in G. Summing up, Algorithm 5 is correct.

Implementation and complexity of Algorithm 5

The data structures involved in Algorithm 5 are a little harder than those in Algorithm 4. The input graph G is implemented with adjacency lists, i.e., the list N (v) is stored for each v ∈ V (G). While N (v) is being iterated, say the next vertex is w, O(1) time access to the position that v occupies in N (w) is required. This can be achieved by keeping a pointer to this position paired with w in N (v). The value of σ(v) is stored together with the vertex v. Given a vertex v, O(1) time access to the set

is stored together with v. A list with the elements of X(v, w) is stored for every vw ∈ E(G). The list X(v, w) has to be obtained in O(1) time while w is being examined in a traversal of N (v). Thus, X(v, w) is also paired with w in N (v). Furthermore, for each z ∈ X(v, w), while traversing N (z) with v as the next vertex, the list X(v, w) has to be accessed in O(1) time. So, a reference x(z, v) pointing to X(v, w) is paired together with v in the list N (z). Recall that {X(v, w)} w∈N (v) is a partition of N (v); indeed, z belongs only to X(v, σ(z)). Thus there is a unique pointer x(z, v) associated with v in N (z). Finally, sets N 1 , N 2 are implemented as n-position vectors so that membership can be tested in O(1) time.

Consider the time complexity of Algorithm 5. To compute σ at Step 2 we first set σ(v) as the outneighbor of v in U (G) by calling Algorithm 4; next, we traverse the family S given by method C4 in [START_REF] Chiba | Arboricity and subgraph listing algorithms[END_REF] so as to update the values of σ accordingly. All these steps take O(mα(G)) time. Next, by traversing V (G), we compute children(v) in O(n) time. For computing the sets X(v, w) at Step 3, for a given v ∈ V (G), we use a three step procedure. First, we traverse N (v) and set X(v, w) = ∅, for each w ∈ N (v). Second, we sort N (v) according to the value of σ, i.e., w appears before z in N (v) only if σ(w) ≥ σ(z). Third, we traverse N (v) once again and, for each w ∈ N (v), we insert w into X(v, σ(w)). These steps take O(d(v)) time each; in particular, the third step can be done as in a merging procedure, because N (v) is sorted according to the values of σ. Therefore, Step 3 takes O(n + m) time. Before executing Step 4, we should update the values of the pointers x(z, v). For this, we traverse each N (v) once again as in the merging step and, when z is being traversed so as to be inserted in X(v, w), we access the position of v inside N (z) in O(1) time, and set x(z, v) to point to X(v, w). Therefore, the update of the x pointers takes O(n + m) time as well. To evaluate the time required by Loop 4-9, consider a vertex v i ∈ V (G).

Step 5 requires only a traversal of N (v i ), so it takes O(d(v i )). For Step 6, it is enough to traverse N (w), for each w ∈ N 1 , while σ is accessed in O(1) time. Therefore, Step 5 takes O( w∈N (vi) d(w)) time. Steps 7 and 8 are implemented together, as follows. For Step 7, we traverse each w 2 ∈ N (w 1 ) ∩ N 2 , for every w 1 ∈ N 1 , and mark every vertex w 3 ∈ X(w 2 , σ(w 1 )) \ N 1 with the value (w 1 , w 2 ). The condition at Step 8 is true for v i if and only if some vertex w 3 is marked twice. Recall Dom(v 2 ). Then, there are two vertices w 1 ∈ B 1 and w 2 ∈ B 2 that do not dominate v 1 and v 2 , respectively. On the other hand, since v 1 < w 1 and v 2 < w 2 , we obtain that v 1 and v 2 do not dominate w 1 and w 2 , respectively. But this implies that v 1 , v 2 , w 1 , w 2 is a non-dominated C 4 of G, a contradiction. Therefore, without loss of generality, we may assume that B 1 ⊆ Dom(v 1 ). Now, as B is maximal, it follows that all the vertices that dominate v 1 are included in B 1 and all the neighbors of v 1 are included in B 2 .

The converse is trivial. 2 Corollary 6.2 A C 4 -dominated graph with no triangles has at most n maximal bicliques.

The following lemma shows how to avoid the listing of duplicate maximal bicliques. Lemma 6.3 Let G be a degree ordered graph that is C 4 -dominated and has no triangles nor twins, and v ∈ V (G). Then B(v) = B(w) for some w ∈ MAX(v) if and only if v is a repeated vertex. ) space algorithm for enumerating all the maximal bicliques of G. First, find the set R of repeated vertices by using the domination matrix; then, output B(v) for every v ∈ V (G)\R. In the remaining of this section, we show an O(mα(G)+o) time and O(mα(G)) space algorithm for enumerating all the maximal bicliques of G, where o = v∈V (G) |B(v)| is the size of the output. Our main tool is, in this case, a digraph that encodes all the dominations of the input graph as paths. This digraph is obtained from the squares domination digraph S(G) by adding all the missing dominations.

Recall that S(G) is obtained from U (G) by inserting the edge w → v, for every safe (v, w) ∈ S. Say that w ∈ V (G) is degenerated when w has no out-neighbors in S(G) and N (w) ⊆ MAX(w). We define the dominator set of w according to the following rules. If L(S) = {w} for some S ∈ S, then the dominator set of w is empty. Otherwise, the dominator set of w is N (z) \ {w}, where z = min N (w).

The following lemma shows that degenerated vertices, together with their dominator sets, are all we need to build the domination digraph from S(G). Lemma 6.4 Let G be a degree ordered graph that is C 4 -dominated and has no triangles nor twins, and w ∈ V (G) be degenerated. Then, w is dominated by v ∈ V (G) if and only if v belongs to the dominator set of w.

Proof: Suppose first that w is dominated by v ∈ V (G), and let z = min N (w). Observe that v < z; otherwise, (v, w) would be a safe triple, contradicting the fact that w has no out-neighbors in S(G). Then, since v dominates w, it follows that v ∈ L(S) for every S ∈ S such that w ∈ L(S). Therefore, Algorithm 6 Maximal bicliques of a C 4 -dominated graph with no triangles. Input: a degree ordered graph G that is C 4 -dominated and has no triangles nor twins. Output: a listing, without duplicates, of all the maximal bicliques in G.

1. Compute the domination matrix D(G).

2. For each v, set dom(v) as the number of ancestors of v in D(G).

Set

Complexity of Algorithm 6

The following observation is useful in the complexity analysis. Proposition 6.7 If G is a degree ordered graph that is C 4 -dominated and has no triangles nor twins, then D(G) has at most 2m edges more than S(G).

Proof: By definition, if w → v is and edge that belongs to D(G) and does not belong to S(G), then w is a degenerated vertex and v belongs to the dominator set of w. Recall that, by Theorem 6.5, the dominator set of w is Dom(w), because w has no out-neighbors in S(G).

Suppose, to obtain a contradiction, that w 1 and w 2 are degenerated vertices with nonempty dominator sets, and call z 1 = min N (w 1 ) and z 2 = min N (w 2 ). If z 1 = z 2 , then w 1 ∈ N (z 2 ) \ w 2 = Dom(w 1 ); analogously, w 2 ∈ Dom(w 1 ). But this contradicts the fact that w 1 and w 2 are not twins. Consequently,

Matrix D(G) can be computed with a five steps procedure, as follows. First, call Algorithm 4 so as to obtain U (G). Second, traverse each S ∈ S as in Algorithm 4 so as to determine whether S is safe or not, and, if S is safe, insert w(S) → v(S) into U (G) to obtain S(G). Third, find and mark all the degenerated vertices, by traversing each w ∈ V (G) while querying whether w has out-neighbors in S(G) and N (w) ⊆ MAX(w). Forth, find those degenerated vertices with nonempty Dom, by removing the mark to all those vertices that belong to L(S), for some S ∈ S such that |L(S)| = 1. This forth step only requires the traversal of S. Finally, D(G) is obtained by inserting an edge w → v into S(G), for every marked w and every v ∈ Dom(w). By Proposition 6.7, O(m) edges are inserted into S(G) in this last step. So, since the first four steps take O(α(G)m) time, Step 1 of Algorithm 6 takes O(α(G)m) time.

Step 2 can be easily implemented so as to run in O(α(G)m) time, by observing that, by Theorem As for the space complexity, D(G) is the heaviest structure stored by Algorithm 6. Thus, Algorithm 6 requires O(α(G)m) space by Proposition 6.7.

Some biclique problems

Theorems 6.1 and 6.5 can also be used to solve many problems that involve finding a biclique with a certain property. Just observe that |Dom(v)| can be computed in O(α(G)m) time and O(n + m) space. Indeed,


Mariusz Grech
email: mariusz.grech@math.uni.wroc.pl

Andrzej Kisielewicz
email: andrzej.kisielewicz@math.uni.wroc.pl

All totally symmetric colored graphs

Keywords: colored graph, symmetric graph, homogeneous factorization

In this paper we describe all edge-colored graphs that are fully symmetric with respect to colors and transitive on every set of edges of the same color. They correspond to fully symmetric homogeneous factorizations of complete graphs. Our description completes the work done in our previous paper, where we have shown, in particular, that there are no such graphs with more than 5 colors. Using some recent results, with a help of computer, we settle all the cases that was left open in the previous paper.

Introduction

A k-colored graph G = (V, ψ) on a set of vertices V is the complete graph on V together with a function ψ from the set of edges onto the set of colors {0, 1, . . . , k -1}. The automorphism group Aut(G) of G is the set of permutations of V preserving the colors of the edges. The extended automorphism group Ext(G) is the set of permutations of V preserving the partition into the colors. Obviously, Aut(G) is a normal subgroup of Ext(G). Moreover, the factor group Ext(G)/Aut(G) may be considered as one acting on the set of colors, and as such is called the symmetry group of colors of G.

A graph G is called edge-transitive if Aut(G) acts transitively on each set of the edges of the same color, and is called arc-transitive (or strongly edge-transitive) if Aut(G) acts transitively on each set of ordered pairs of vertices corresponding to a set of edges of the same color. It is called color-symmetric, if Ext(G) acts as the symmetric group on the set of colors. If G is both color-symmetric and edge-transitive (complete) graph, then it is called totally symmetric, or TSC-graph, in short. In the previous paper [START_REF] Grech | Totally symmetric colored graphs[END_REF], we have proved that TSC-graphs may occur only for less than 6 colors. In this paper we give a complete description of such graphs. In particular, we have proved that such graphs are arc-transitive. For two colors these are self-complementary symmetric graphs, which have been recently described by Peisert [START_REF] Peisert | All self-complementary symmetric graphs[END_REF]. Our result may be viewed as a natural generalization of Peisert's result.

Problems closely related to the subject of this paper have been studied under various names. In [START_REF] Sibley | On classifying finite edge colored graphs with two transitive automorphism groups[END_REF], T. Sibley classifies edge colored graphs with 2-transitive extended automorphism group Ext(G) (he calls this group the automorphism group, and only mention Aut(G) calling it the group of isometries). Colored graphs with transitive Aut(G) have been considered by Chen and Teh in [START_REF] Chen | Constructions of point-colour-symmetric graphs[END_REF]; they call them point-color symmetric graphs. Ashbacher [START_REF] Aschbacher | Chromatic geometry[END_REF] uses the name rainbows for such structures. Various highly-symmetrical structures in this class have been intensively studied using results based on the classification of finite simple groups (see e.g. [START_REF] Cameron | On groups of degree n and n -1, and highly-symmetric edge colourings[END_REF][START_REF] Cameron | One-factorizations of complete graphs with a doubly transitive automorphism group[END_REF][START_REF] Giudici | Homogeneous factorizations of graphs and digraphs[END_REF][START_REF] Kantor | Homogeneous designs and geometric lattices[END_REF][START_REF] Li | On partitioning the orbitals of a transitive permutation group[END_REF][START_REF] Muzychuk | On Sylow subgraphs of vertex-transitive self-complementary graphs[END_REF][START_REF] Potočnik | Brick assignments and homogeneously almost self-complementary graphs[END_REF].

The most interesting colored graphs arise from factorizations of complete graphs, that is partitions of the edges into factors that correspond to spanning subgraphs (not necessarily connected). Isomorphic factorizations, coloring the edges of a graph so that the colored subgraphs are isomorphic, have been introduced and studied in a series of papers by Harary, Robinson and Wormald (cf. [START_REF] Harary | Isomorphic Factorisations I: Complete Graphs[END_REF][START_REF] Harary | Isomorphic Factorisations X: Unsolved problems[END_REF]). A factorization of a complete graph is homogeneous if there are subgroups H < G ≤ S n such that H is vertex-transitive and fixes each factor setwise, and G permutes the factors transitively (in particular, the factors are isomorphic). TSC-graphs correspond to those factorizations where H is edge-transitive and G permutes factors symmetrically. Recently, in [START_REF] Li | Homogeneous factorizations of complete graphs with edgetransitive factors[END_REF], Li, Lim and Praeger have classified all homogeneous factorizations with H being edge-transitive. Their result helped us to finish our study and get the following complete description of totally symmetric colored graphs.

Theorem. If G is an edge-transitive color-symmetric k-colored complete graph, then G is arc-transitive and k ≤ 5. Moreover, one of the following cases holds:

(i) k = 5 and G = F 5 (4 2 ) or G = H 5 (3 4 ); (ii) k = 4 and G = F 4 (3 2 );
(iii) k = 3 and G belongs to an infinite family of generalized Paley graphs

GP 3 (q) or G = G 3 (5 2 ) or G = G 3 (11 2 );
(iv) k = 2 and G belongs to an infinite family of Paley graphs PG(q) or Peisert graphs PG * (q), or else G = G(23 2 ).

All graphs mentioned in the theorem are defined in the next section. The result is an improvement on a theorem in [START_REF] Grech | Totally symmetric colored graphs[END_REF], which is also presented here for convenience as Theorem 2.1.

We note that this description is something much stronger than just a classification. In a sense one may say that our description is contained in the results classifying finite simple groups, rank 3-groups, and homogeneous factorizations. A good example of what makes a difference here is that (as we shall see in the remainder of the paper) all classifications show the possibility of existence of a 5-colored TSC-graph on 2 8 vertices. Only combining suitable knowledge with heavy computations has allowed to learn that such an object, in fact, does not exists.

The paper is organized as follows. In Section 2 we classify and give definitions of totally symmetric graphs. In Section 3, we summarize and recall results needed in our proof. Then, in the three following sections we consider 4-, 5and 3-colored TSC-graphs, respectively, which are the cases (ii), (i), and (iii) of the theorem above. The 2-colored TSC-graphs, as we have already mentioned, are described completely in [START_REF] Peisert | All self-complementary symmetric graphs[END_REF]. Finally, in Section 7 we present computations that allowed to settle the most complicated cases that arose during consideration in Section 5.

Definitions of TSC-graphs

We assume that the reader is familiar with general terminology of finite fields, vector spaces and permutation groups (as used, e.g., in [START_REF] Cameron | Permutation Groups[END_REF][START_REF] Dixon | Permutation Groups[END_REF]). We start from 2-colored graphs, which correspond naturally to simple graphs (with non-edges treated as the second color). In this paper simple graphs are identified with their 2-colored equivalents. Whenever we consider a finite field F q (q = p r ), by ω we denote a fixed primitive root of F q .

Simple graphs.

Totally symmetric 2-colored graphs correspond to simple graphs that are symmetric and self-complementary. They have been fully described in [START_REF] Peisert | All self-complementary symmetric graphs[END_REF]. Recall first that the Paley graph PG(q), where q = 1(mod 4), is one whose vertex set is F q , and two distinct elements are adjacent, if their difference is a square in F q (i.e., if it is of the form ω 2k ). If in addition, p = 3(mod 4) (and consequently, r is even), then the Peisert graph PG * (q) is one whose vertex set is F q , and two elements are adjacent, if their difference is of the form ω j , where j = 0, 1(mod 4). The constructions above do not depend on the choice of the primitive root. Moreover, PG(q) is isomorphic with PG * (q) only if q = 9. For details see [START_REF] Peisert | All self-complementary symmetric graphs[END_REF].

An exceptional self-complementary symmetric graph G( 232 ) has a rather complicated definition. It can be found in [START_REF] Peisert | All self-complementary symmetric graphs[END_REF].

Generalized Paley graphs

Following the definition of Paley graphs we define now their 3-colored counterparts. Let p = 2(mod 3), q = p r , and q = 1(mod 3) (which is equivalent to r being even). Let GP 3 (q) denote 3-colored graph whose vertex set is F q , and the edge between two distinct elements has color i (i = 0, 1, 2) if their difference is of the form ω 3m+i . It is not difficult to see that this definition does not depend on the choice of the primitive root (see. [START_REF] Grech | Totally symmetric colored graphs[END_REF]), and the graph may be viewed as the orbital graph of the subgroup of the affine group generated by translations and multiplication by ω 3 . In [START_REF] Li | Homogeneous factorizations of complete graphs with edgetransitive factors[END_REF] such graphs appear as cyclotomic partition Cyc(q, k) of K q and k = 3. In general, graphs corresponding to such partitions are colortransitive. The case specified here (k = 3, p = 2(mod 3), r even) is the only one with k > 2, when they are color-symmetric.

Following [START_REF] Li | Homogeneous factorizations of complete graphs with edgetransitive factors[END_REF] we define also generalized Paley graphs with more colors. Namely, for each k > 2 and q = 1(modk), and such that either p = 2 or (q -1)/k is even we define GP k (q) as k-colored graph whose vertex set is F q , and the edge between two distinct elements has color i (i = 0, . . . , k -1) if their difference is of the form ω km+i . This correspond to cyclotomic partitions Cyc(q, k) in [START_REF] Li | Homogeneous factorizations of complete graphs with edgetransitive factors[END_REF]. We note that our usage of the term "generalized Paley graph" is slightly different: we mean the resulting colored graph, while Li at al. [START_REF] Li | Homogeneous factorizations of complete graphs with edgetransitive factors[END_REF] mean the simple Caley graph occurring as the factor of the partition. We needed to write a special computer program to make sure that for k > 3 there is no TSC-graph in this family (see Section 7).

Graphs determined by directions in vector space.

We consider now finite vector spaces F d q constructed from finite fields F q . For d > 1, by F k (q d ) we denote the k-colored graph defined on F d q , with k = (q d -1)/(q -1), whose colors are determined naturally by k independent directions in the space. Scalar multiplication and addition (translations) preserve colors and move vector (0, v) to any vector in the direction generated by (0, v). This shows that F k (q d ) is arc-transitive. Linear automorphisms of F d q act transitively on directions, which shows that F k (q d ) is color-transitive.

One may check directly that three of these graphs, F 5 (4 2 ), F 4 (3 2 ), F 3 (2 2 ) are color-symmetric. The last graph is isomorphic to GP 3 (2 2 ) and its automorphism group is abstractly isomorphic to the Klein four-group. This group is the only known permutation group that is orbit closed but is not a relation group (that is, closed in its action on the subsets of the underlying set Ω, and not the automorphism group of any hypergraph on Ω; [START_REF] Volta | Orbit equivalence and permutation groups defined by unordered relations[END_REF][START_REF] Kisielewicz | Symmetry groups of boolean functions and constructions of permutation groups[END_REF]; note that Corollary 5.3 in [START_REF] Volta | Orbit equivalence and permutation groups defined by unordered relations[END_REF] has wrong proof).

Exceptional 3-colored TSC-graphs.

There are two further 3-colored TSC-graphs defined in a similar way on vector spaces F 2 5 and

F 2 11 . The vertex set of G 3 (5 2 ) is V = F 2 5 .
It has 6 directions determined by vectors starting in (0, 0) and ending in (1, 0), (0, 1), (1, 1), (2, 1), (3, 1), [START_REF] Cameron | One-factorizations of complete graphs with a doubly transitive automorphism group[END_REF][START_REF] Aschbacher | Chromatic geometry[END_REF]. The edges in directions determined by (1, 0) and (0, 1) have color 0, those in directions determined by (1, 1) and (2, 1) have color 1, and the remaining have color 2. In other words, the graph is determined by the partition:

[(1, 0), (0, 1)], [(1, 1), (2, 1)], [(3, 1), (4, 1)]. Graph G 3 (11 2 ) has an analogous definition. The vertex set of G 3 (11 2 ) is V = F 2
11 . It has 12 directions determined by vectors starting in (0, 0) and ending in (1, 0) or (i, 1) for i = 0, . . . 10. The graph is then determined by the partition [(1, 0), (0, 1), (1, 1), (10, 1)], [(2, 1), (3, 1), (5, 1), (7, 1)], [(4, 1), (6, 1), (8, 1), [START_REF] Foulser | The flag-transitive collineation groups of the finite Desarguesian affine planes[END_REF][START_REF] Aschbacher | Chromatic geometry[END_REF]].

The fact that these graphs are color-symmetric is proved in Section 6, where also the automorphism groups of these graphs are presented.

Colored Hamming graph.

Let us consider the exceptional affine 2-transitive group M ≤ AGL 4 (3) with M 0 > R = 2 1+4 given by Hering's Theorem in [START_REF] Liebeck | The affine permutation groups of rank three[END_REF]Table 10] (cf. also [21, p. 484

, Case R = R 2 2 ]
). Let H 5 (3 4 ) be the colored graph determined by the orbitals of this group. Then combining Theorem 1.1 with Proposition 5.9 of [START_REF] Li | Homogeneous factorizations of complete graphs with edgetransitive factors[END_REF] we see that H 5 (3 4 ) is a 5-colored TCS-graph. The corresponding factorization is considered in detail in [START_REF] Lim | Arc-transitive homogeneous factorizations and affine planes[END_REF]. In particular, it is observed that factors are isomorphic with Hamming graph H(2, 9) (both in [START_REF] Lim | Arc-transitive homogeneous factorizations and affine planes[END_REF] and [START_REF] Li | Homogeneous factorizations of complete graphs with edgetransitive factors[END_REF] the notation H(9, 2) is used, but this seems to be a mistake).

Proof

We start by recalling the results we apply in this paper. First, let us recall the results of [START_REF] Grech | Totally symmetric colored graphs[END_REF] summarized suitably as follows:

Theorem 3.1 If G is a k-colored TSC-graph then k ≤ 5
and G is arc-transitive. In addition, for k > 2 we have the following.

(i) F 5 (4 2 ) is the unique 5-colored TSC-graph on 16 vertices. Except, possibly, for n = 2 8 , 3 4 or 7 4 there is no other 5-colored TSC-graph on n vertices.

(ii) F 4 (3 2
) is the unique 4-colored TSC-graph on 9 vertices. Except, possibly, for n = 3 4 there is no other 4-colored TSC-graph on n vertices.

(iii) Except for the known infinite family of 3-colored TSC-graphs (generalized Paley graphs), there are only finitely many other 3-colored TSC-graphs with the number of vertices belonging to the set {2 4 , 2 6 , 5 2 , 11 2 , 17 2 , 23 2 , 89 2 }.

Combining the above with [18, Theorem 1.1] (and careful inspecting Tables 2 and3 of [START_REF] Li | Homogeneous factorizations of complete graphs with edgetransitive factors[END_REF]), we see that almost all TSC-graphs G have Aut(G) contained in one-dimensional semilinear affine group. Let G be a TSC-graph satisfying (iii). Since Aut(G) contains translations, we may restrict to stabilizers of zero: A = Aut(G) 0 and M 0 . Then A ≤ M 0 ≤ ΓL 1 (n). This makes possible to apply Foulser's description of one-dimensional semilinear groups [START_REF] Foulser | The flag-transitive collineation groups of the finite Desarguesian affine planes[END_REF][START_REF] Foulser | Solvable, flag-transitive collineation groups[END_REF]. Let us recall briefly the facts we shall need.

Let ω be a primitive root of the underlying field F q (q = p r ), and at the same time, let it denotes the scalar multiplication by ω, and let α be the generating field automorphism α : x → x p . Then ΓL 1 (p r ) = ω, α is the semidirect product of the normal subgroup ω by the subgroup α . In particular, every element of g ∈ ΓL 1 (p r ) has a unique presentation as g = ω e α s for some 0 ≤ e < p r -1, 0 ≤ s < r. (Alternatively, one may take 0 < s ≤ r which is more suitable for the lemma below). Moreover, integers d, e, s satisfying the conditions above are unique, and the presentation H = ω d , ω e α s is called the standard form. In addition, the proof shows that each of d and s < r is in fact the least positive integer such that H = ω d , ω e α s for any d, e, s. Moreover, H is a subdirect product of the normal subgroup ω d by the (another cyclic) subgroup ω e α s . The cardinality |H| = (p r -1)r/ds. We note also that αω = ω p α.

In our situation, A acts on the set {ω 0 , . . . , ω p r -1 } of nonzero elements of the field F q . It has k equal orbits corresponding to orbitals of Aut(G), representing colors of G. Thus we may consider the nonzero elements of F q as colored: the color of ω i ∈ F q is the color of the edge (0, ω i ). We will refer to such an edge as the edge ω i . By Foulser's description, A = ω d , ω e α s and M 0 = ω d1 , ω e1 α s1 , where d 1 |d, and if s 1 > 0, then s 1 |s. Moreover if s > 0 then s 1 > 0.

In the following sections we show that these conditions are very strong and leave little space for existence of suitable objects. The description presented in the main theorem follows directly from the lemmas in the subsequent sections combined with Theorem 3.1 and the Peisert's result in [START_REF] Peisert | All self-complementary symmetric graphs[END_REF].

TSC-graphs with colors

We start from the case (ii) of Theorem 3.1. We prove the following. Proof: Suppose, to the contrary, that G is a 4-color TSC-graph on 3 4 vertices. By Corollary 3.2 Aut(G) is an affine group satisfying conditions given in (iii). We apply the notation given above. In this case k = 4, n = 3 4 , p = 3, r = 4. In particular, α : x → x 3 .

By cardinality formula |A| = 80 • 4/ds. Since A is transitive on each color, (80/4) divides |A|. It follows that ds|16. Since, A has four orbits, d ≥ 4. Thus, we have three cases to consider.

Case 1: d = 16 and s = 1.

Here A = ω 16 , ω e α . Permutation ω 16 has 16 orbits represented by elements ω i (i = 0, . . . , 15). Since A has 4 equal orbits, for each such an orbit, permutation ω e α should "glue together" 4 ω 16 -orbits, that is, it should act on ω 16 -orbits as a product of 4 cycles of length 4. It means, that for each i = 0, 1, . . . , 15, the 4 consecutive images of element ω i by permutation ω e α should belong to 4 different orbits. We compute two of these images: ω e α(ω i ) = ω 3i+e and (ω e α) 2 (ω i ) = ω 9i+4e . By Lemma 3.3(iii), it follows that e must be divisible by 2, so e = 2f for some f . Thus, (ω e α) 2 (ω i ) = ω 9i+8f . It should belong to a different on ω 16 -orbit than ω i itself. It means that 9i + 8f is different from i modulo 16. Applied for i = 0, 1 it means that (modulo 16) 8f is different from 0, and 9 + 8f is different from 1, which is impossible.

Case 2: d = 8 and s ∈ {1, 2}. Assume first that s = 1. In this case ω 8 has 8 orbits, and permutation ω e α should "glue together" 4 pairs of such orbits. The consecutive images of ω 0 by ω e α are ω e and ω 4e , which implies that e = 2f for some f . Now, the images ω e α(ω i ) = ω 3i+2f should be in a different ω 8 -orbit than ω i , for each i, which means that 3i + 2f is different from i modulo 8. It follows that 2i + 2f is different from 0 modulo 8, that is, i + f is different from 0 modulo 4, for each i. Yet, for each f = 0, 1, 2, 3, there exists i such that i + f = 0 modulo 4, a contradiction.

If s = 2, then by Lemma 3.3(3), e = 0 or e = 4. Also, observe that α 2 : x → x 9 preserves the orbits of ω 8 . Hence α 2 ∈ A. Now, A = ω 8 , α 2 , since the latter has 8 orbits. On the other hand, α 2 / ∈ ω 8 , ω 4 α 2 , a contradiction.

Case 3: d = 4. As above, we see that α 2 preserves the orbits of ω 4 . Since no other permutation ω e α s preserves these orbits, A = ω 4 , α 2 . Here, we need a deeper argument, exploiting total symmetricity. Since G is a 4-color TSC-graph, by identifying any two pairs of colors we should obtain 2-color TSCgraphs that are isomorphic. Yet, identifying color 0 with color 2 and color 1 with color 3, we obtain Paley graph PG(3 4 ), while identifying color 0 with color 1 and color 2 with color 3, we obtain Peisert graph PG * (3 4 ). These graphs are not isomorphic, and thus we have a contradiction. 2

TSC-graphs with colors

In a quite similar way we consider now the case (i) of Theorem 3.1 with k = 5. Here A = ω 20 , ω e α . Permutation ω 20 has 20 orbits, and ω e α should act as a product of 5 cycles of length 4 on ω 20 -orbits. We compute: ω e α(ω i ) = ω 7i+e and (ω e α) 2 (ω i ) = ω 49i+8e . The value 49i + 8f should be different from i modulo 16, which means that 9i + 8f is different from i, that is 8i + 8f is different form 0 modulo 20. Consequently, for some f , and for all i, i + f should be different from 0 modulo 5, which is impossible.

Case 2: d = 10 and s ∈ {1, 2}. Now ω e α should act as a product of 5 transpositions on ω 10 -orbits. Hence, for s = 1, (ω e α) 2 (ω i ) = ω 49i+8e is the identity on these orbits. Yet, for i = 0, 1 we have 9i + 8e = 8e and 9 + 8e, respectively. It follows that 5 divides e and, consequently, 9 + 8 • 5f is equal 1 modulo 10, for some f , which is a contradiction.

For s = 2, ω e α 2 (ω i ) = ω 49i+e . For e odd, this yields a required product of transpositions, so we need a deeper argument to get a contradiction in this case.

We make use of the larger group M in Corollary 3.2(3). Since M 0 permutes the colors of G transitively, and n = 7, M 0 contains in particular a cyclic permutation of colors. Without loss of generality we may assume that M is an extensions of Aut(G) by a single permutation c permuting colors cyclically. We have M 0 = ω d1 , ω e1 α s1 , where d 1 |10, and the index [M 0 : A] = 5. The only possibility is M 0 = ω 2 , ω e α 2 . It follows that ω 2 is a cyclic permutation of colors of order 5.

Now, the images of ω 0 and ω 2 by ω e α 2 are, respectively, in ω 10 -orbits represented by ω e and ω e+8 . In, particular the corresponding pairs have the same colors. It follows, that ω 2 ω e = ω e+2 should have the same color as ω e+8 . This contradicts the fact that ω 2 is a cyclic permutation of colors of order 5.

Case 3. d = 5 and s ∈ {1, 2, 4}. Here ω 5 -orbits have to correspond to 5 colors. We check that ω e α s does not preserve ω 5 -orbits unless e = 0 and s = 4. Thus, A = ω 5 . Note, that in this case, ω permutes ω 5 -orbits cyclically, so we cannot obtain a contradiction with the methods applied so far. Adding to A translations, we obtain a group whose orbitals form a 5-colored graph. This is just the only exception pointed out in the formulation of the theorem.

2

We observe that this exceptional graph is the generalized Paley graph GP 5 (7 4 ) defined in Section 2. One may check that the whole group AΓL 1 (7 4 ) preserves colors of GP 5 (7 4 ), which suggests that it may be a TSC-graph with the automorphism group containing AΓL 1 (7 4 ) (and contained in AΓL 4 [START_REF] Volta | Orbit equivalence and permutation groups defined by unordered relations[END_REF]). Note that we are able easily to compute this graph and store it in computer memory, but since it has 2401 vertices, computing its automorphism group is beyond the capabilities of modern computer technology. Only combining suitably the computational power with the knowledge we possess makes possible to settle the case. This will be done in the next section. Lemma 5.2 There is at least one and at most two 5-colored TSC-graph on 3 4 vertices.

Proof: One of such graphs is H 5 (3 4 ) described in Section 2. By Corollary 3.2, for every other 5-colored TSC-graph G on 3 4 , Aut(G) is an affine group satisfying conditions given in (iii).

In this case k = 5, p = 3, and r = 4. The cardinality |A| = (3 4 -1) • 4/ds. Since Aut(G) is arc transitive, (3 4 -1)/5 divides |A|. It follows that ds|20. Since, A has five orbits, d ≥ 5. The remaining of the proof is essentially the same as that for n = 7 4 . We leave it to the reader. Again, similarly as in the previous case, the only unsettled case is A = ω 5 acting on nonzero elements of F 81 .

2

As before, the exceptional graph is the generalized Paley graph, GP 5 (3 4 ), and one may check that the whole group AΓL 1 (3 4 ) preserves colors. So, we need other methods to check this case. Here, GP 5 (3 4 ) has "only" 81 vertices, so one could try to check it using existing computation tools for permutation groups. Yet, we will do it more efficiently applying the same approach as in the case of GP 5 (7 4 ). This is presented in the next section. The last case of Theorem 3.1(i) to consider is that for n = 2 Again we check that for A to have 5 orbits, we need to have e = 0 and s = 0 or 4. Since α 4 : x → x 16 preserves ω 5 -orbits, it follows that the only possibility is A = ω 5 , α 4 , and the possible exception mentioned in the formulation of the lemma is, again, the generalized Paley graph GP 5 (2 8 ). 2

TSC-graphs with 3 colors

Before we deal with the three unsettled cases of the previous section, we complete our investigation considering the case k = 3. In the three lemmas below we use the fact that, by Corollary 3.2, Aut(G) is an affine group satisfying conditions given in (iii). As before we use the notation of Section 3. Here, again, we make use of the facts that |A| = 2(p 2 -1)/d and (p 2 -1)/3 divides |A|. Hence d|6. Since d ≥ 3, we have two cases d = 6 or d = 3. The proof is the same in each case p = 17, 23, 89, since in each case p = 5 modulo 6 (in particular, p = 2 modulo 3).

Case 1. d = 3. Since A should have exactly 3 orbits, ω e α should preserve ω 3 -orbits. Yet, the image of ω i by ω e α is ω j , where j = pi + e = 2i + e modulo 3. It follows that i = 2i + e, and consequently, i = -e modulo 3. This should be satisfied for each i and a field e, a contradiction.

Case 2. d = 6. Here, we look for e such that ω e α acts as a product of three transpositions on ω 6 -orbits. Now, the image of ω i by ω e α is ω j , where j = e + 5i = e -i modulo 6. It follows that A has exactly three orbits only when e is odd.

Here we need again a deeper argument, analogous to that applied in Case 2 of Lemma 5.1. In the same way we infer that there exists a group M 0 = ω d1 , ω e1 α s1 , where d 1 |6, and the index [M 0 : A] = 3. The only possibility is M 0 = ω 2 , ω e α . It follows that ω 2 is a cyclic permutation of colors of order 3.

Now, the images of ω 0 , ω 1 and ω 2 by ω e α are, respectively, in ω 3 -orbits represented by ω e , ω e+2 and ω e+1 . This contradicts the fact that ω 2 is a cyclic permutation of colors of order 3.

2

It remains to consider exceptional cases of n = 5 2 and 11 2 . We consider each of these cases separately, but before, we establish a more general result we need here. By Theorem 2.1 of [START_REF] Grech | Totally symmetric colored graphs[END_REF] we know that if G is a k-colored TSC-graph then Aut(G) is an affine group. It follows we may speak of the (finite) vector space V associated with G, and consequently, of sets of vertices forming lines in V . We prove that for k > 2 lines are monochromatic in the following sense. Lemma 6.4 If G is a 3-colored TSC-graph, and V a vector space associated with G, then for each onedimensional subspace L of V , if v, u ∈ L, v, u = 0, then the edges (0, v) and (0, u) have the same color.

Proof: We make use of the fact that by the proof of Theorem 2.1 of [START_REF] Grech | Totally symmetric colored graphs[END_REF] not only Aut(G), but also Ext(G) is an affine group (see also [START_REF] Sibley | On classifying finite edge colored graphs with two transitive automorphism groups[END_REF]Theorem 15]). This means that Ext(G) 0 ≤ GL r (p), where |V | = p r . In particular, permutations in Ext(G) preserve lines.

Let L = {0, x 1 , . . . , x p-1 }, and x 1 (that is, (0, x 1 )) has color 0. Let f ∈ Ext(G) 0 be a permutation of vertices that is a transposition of colors 1 and 2. Since color 0 is fixed, and Aut(G) is transitive on each color, we may assume that f fixes x 1 , as well. Consequently, f (L) = L. Now assume that there is a vertex x i in L which is colored 1. It follows that the number of vertices x i ∈ L colored 1 is the same as that colored 2. Since the choice of colors is arbitrary, it follows that all the colors are represented in L in the same number. This contradicts the fact that, by Theorem 3.1, p = 2(mod 3). 2 Lemma 6.5 The generalized Paley graph GP 3 (5 2 ) and the graph G 3 (5 2 ) defined in Section 2 are the only two nonisomorphic 3-colored TSC-graphs on 5 2 vertices.

Proof: Let G be a 3-colored TSC-graph on 5 2 vertices. We first construct the field F 25 taking 2 + x 2 as an irreducible polynomial over F 5 , and ω = 1 + x as a primitive root. Then we have the natural injection of ΓL 1 (25) into GL 2 [START_REF] Cartrysse | The Advanced Encryption Standard: Rijndael, Chapter in Basic methods of cryptography[END_REF] given by

ω -→ 1 3 1 1 , α -→ 1 0 0 -1
The associated vector space V = F 2 5 has six lines (one-dimensional subspaces) determined by vectors (1, 0), (0, 1), (1, 1), (2, 1), [START_REF] Cameron | Permutation Groups[END_REF][START_REF] Aschbacher | Chromatic geometry[END_REF], [START_REF] Cameron | One-factorizations of complete graphs with a doubly transitive automorphism group[END_REF][START_REF] Aschbacher | Chromatic geometry[END_REF]. Taking powers of ω = 1 + x modulo 2 + x 2 , we check that they correspond to the lines containing 1, ω 3 , ω, ω 2 , ω 4 , and ω 5 , respectively. By Lemma 6.4, each line is monochromatic, and consequently, two lines correspond to each color. Without loss of generality we may assume that lines of (1, 0) and (0, 1) have the same color. (This is so because changing a base by conjugation preserve lines, and therefore it is enough to consider only graphs, in a fixed presentation, with base lines of (1, 0) and (0, 1) having the same color). Then one of the lines generated by (2, 1), (3, 1), (4, 1) has to have the same color as [START_REF] Aschbacher | Chromatic geometry[END_REF][START_REF] Aschbacher | Chromatic geometry[END_REF]. This implies that we have at most three nonisomorphic 3-colored TSC-graphs on 5 2 .

The second possibility (lines of (3, 1) and (1, 1) have the same color) leads to a graph G 2 whose Aut(G 2 ) 0 = ω 3 . This group is isomorphic to Z 8 and G 2 is isomorphic to GP 3 (5 2 ). The first possibility (lines of (2, 1) and (1, 1) have the same color) leads to a graph G 1 whose Aut(G 1 ) 0 = ω 6 , ω 3 α . It is not difficult to see that this graph is isomorphic to G 1 . Indeed the permutation of F 2 5 corresponding to the transposition (2, 3) of the underlined field F 5 yields the desired isomorphism.

The last possibility (lines of (4, 1) and (1, 1) have the same color) leads to another 3-colored TSC-graph G 3 on 5 2 vertices. It is straightforward to check that in this case Aut(G 3 ) 0 is generated by matrices Proof: In this case the fact that there are at most two 3-colored TSC-graphs on 11 2 vertices has been established in the proof of [START_REF] Grech | Totally symmetric colored graphs[END_REF]Theorem 5.1]. The second case in that proof is Aut(G) 0 = ω 3 , α 2 < ΓL 1 (11 2 ) (note that in this case α 2 is an identity). This leads to the generalized Paley graph GP (11 2 ). Below, we will use the fact that, in this case, Aut(G) 0 is cyclic and isomorphic to Z 40

2 0 0 2 , 0 1 1 0 , -1 0 0 1 , which is isomorphic to D 4 × Z 2 ,
The other case in the proof of [START_REF] Grech | Totally symmetric colored graphs[END_REF]Theorem 5.1] is Aut(G) 0 = ω 6 , ω 3 α (where ω 3 may be replaced by ω or ω 5 leading to isomorphic graphs). This group is also of order 40 but is isomorphic with the group a, b|a 20 = e, b 2 = a 2 , ba = a 11 b , which is not abelian and therefore not isomorphic to Z 40 . It follows that the graph G determined by the orbitals of the corresponding group is not isomorphic to GP(11 2 ). We still need to prove that it is totally symmetric.

In order to construct the field F 11 2 we take the polynomial 1 + x 2 , which is irreducible over F 11 . As a primitive root we take ω = 6 + 2x. We have twelve lines which contain ω 0 , . . . , ω 11 , respectively. For each i, we compute vector (x, y) belonging to the same line as ω i , and using Aut(G) 0 we determine lines with the same color. The results are presented in Table 1. As we see, this defines graph G 3 (11 2 ) introduced in Section 2. Using the table we may check that the graph is totally symmetric. To this end it is enough to check that the matrix 1 0 0 -1 exchanges colors 1 and 2, while the matrix i vector i vector i vector i vector i vector i vector 0 (1,0)

Computations

In order to check whether the exceptional graphs mentioned in Section 5 are totally symmetric we wrote a dedicated computer program that made an intensive use of the facts about the structure of the graphs we have established. Below, we present the result and the details of the computations.

Theorem 7.1 None of the graphs GP 5 (3 4 ), GP 5 (7 4 ), GP 5 (2 8) is totally symmetric.

The general idea of computations is the same in each case p r = 3 4 , 7 4 , 2 8 . First, we use the fact mentioned in the proof of Lemma 6.4 that the extended automorphism group of a totally symmetric graph is contained in AGL r (p). It follows that we may restrict to stabilizers of 0 anyway, and our aim is to prove that GL r (p) does not permute colors in the symmetric way. Colors of GP 5 (p r ) corresponds to the orbits of A = ω 5 . To fix notation, let us assign color i to the orbit of ω i for i = 0, 1, . . . , 4. It is enough to show that, for instance, no permutation in GL r (p) transposes colors 0 and 1. We make use of the fact that permutations in GL r (p) can be represented by suitable r × r matrices. We have, respectively, 3 16 , 7 16 , and 2 64 matrices to check, which are still too large numbers. So we need to use further facts in order to reduce these numbers. Since now the details of the program differ in each case, we describe them, first, for n = 7 4 .

First, we construct a concrete field on n = 7 4 elements, using the polynomial x 4 +x 3 +x 2 +3 irreducible over F 7 . We check that ω = x is a primitive root of F n , generating the multiplicative group. Computing all the powers ω i we establish the colors of all vectors (a 0 , a 1 , a 2 , a 3 ) = a 0 + a 1 x + a 2 x 2 + a 3 X 3 . In order to prove that the graph determined by the colored vectors is not totally symmetric it is enough to show that there exists a permutation of colors that is not preserved by any linear transformation. For technical reason we demonstrate this for transposition (1, 2) of colors 1 and 2. We note that the since the powers ω 0 , ω 1 , ω 2 are the vectors (1, 0, 0, 0), (0, 1, 0, 0) and (0, 0, 1, 0), respectively, their colors are 0, 1 and 2, respectively. Thus, we are looking for a 4 × 4 matrix B = (a ij ), a ij ∈ F 7 such that for each vector v ∈ F n , v and Bv have the same colors, except for that if v has color 1 then Bv has color 2, v has color 2 then Bv has color 1. Note that since A is transitive on each color, if there is B with the required properties, then there must be one that in addition fixes ω 0 = (1, 0, 0, 0). In other words, we may assume that the first column of B is just (1, 0, 0, 0). Further way to reduce the number of matrices to check is to observe that, since the color of (0, 1, 0, 0) is 1, the second column must be a vector of color 2. Similarly, the third vector must be of color 1, while the fourth column must be a vector of color 3. Since there are (7 4 -1)/5 = 480 vectors of each color we have 480 3 ≈ 11 × 10 7 matrices to generate and check. We wrote a suitable program in C++ and it took some 20 minutes on our PC-computer with a 2GHz processor to get the answer that no matrix satisfies these conditions.

The analogous program for the case of n = 3 4 has obtained the same answer checking 4096 matrices in an instant time. The case n = 2 8 is the hardest one. Here we have (2 8 -1)/5 = 51 vectors for each color, and consequently, 51 7 ≈ 9 × 10 11 matrices to check. To reduce this number we make use of the fact that candidates for each column may be further restricted as follows. The sum of the first and the i-th column, i > 1, must be of the same color as the vector (1, 0, . . . , 0, 1, . . . , 0) with the second 1 on the i-th place. The sum in question may be obtained just by switching the first bite in the vector representing the i-th column. Computations in the field F 2 8 may be also speeded up due to the fact that the underlying field is the so called Rijndael field [START_REF] Cartrysse | The Advanced Encryption Standard: Rijndael, Chapter in Basic methods of cryptography[END_REF], where each vector may be treated as a byte, and consequently bitwise operations may be applied directly. In particular, computing the image of a vector by a matrix reduces to computing the exclusive-OR operation on the set of column-bytes. We were able to reduce the computation time to a few hours to get the answer that no matrix satisfies the required conditions.

Since the answers in all the three cases was negative, we modified the program slightly to make sure it gives correct answers to other related questions. In particular, our program found correctly the matrices permuting colors in a cyclic way and computed the correct cardinalities of the automorphism groups.

Corollary 3 . 2

 32 If G is a k-colored TSC-graph on n vertices mentioned as a possibility in the above theorem, then one of the following holds (i) k = 5 and G = H 5 (3 4 ), (ii) k = 3 and n = 5 2 or n = 11 2 , or else (iii) Aut(G) is an affine group contained in AΓL 1 (n) and there exists larger group M ≤ AΓL 1 (n) such that Aut(G) ≤ M ≤ Ext(G), and M permutes transitively colors of G (that is, orbits of Aut(G)).

Lemma 3 . 3

 33 [START_REF] Foulser | Solvable, flag-transitive collineation groups[END_REF] Lemma 2.1] Let H be a subgroup of ω, α . Then H has the form H = ω d , ω e α s , where d, e, s can be chosen to satisfy the following conditions (i) s > 0 and s|r;(ii) d > 0 and d|(p r -1);(iii) 0 ≤ e < d and d|e(p r -1)/(p s -1).

Lemma 4 . 1

 41 There is no 4-colored TSC-graph on 3 4 vertices.

Lemma 5 . 1

 51 There is at most one 5-colored TSC-graph on 7 4 vertices.Proof: Let G be a 4-color TSC-graph on 7 4 vertices. By Corollary 3.2 Aut(G) is an affine group satisfying conditions given in (iii). In this case k = 5, p = 7, and r = 4. The cardinality |A| = (7 4 -1) • 4/ds. Since Aut(G) is arc transitive, (7 4 -1)/5 divides |A|. It follows that ds|20. Since, A has five orbits, d ≥ 5.Case 1: d = 20 and s = 1.

8 . 5 . 3

 853 Lemma There is at most one 5-colored TSC-graph on 2 8 vertices.Proof: If G be a 5-color TSC-graph on 2 8 vertices, then by Corollary 3.2, Aut(G) is an affine group satisfying conditions given in (iii). In this case k = 5, p = 2, and r = 8. Using cardinality arguments we have that |A| = (2 8 -1) • 8/ds, and by arc transitivity, (2 8 -1)/5 divides |A|. It follows that ds|40. Since, A has five orbits, d ≥ 5, and since (by Lemma 3.3(ii)) d divides 2 8 -1 = 255 = 5 • 51, it follows that we have only one possibility d = 5.

Lemma 6 . 1 2 Lemma 6 . 2 2 Lemma 6 . 3

 61262263 The generalized Paley graph GP(2 4 ) is the only 3-colored TSC-graph on 2 4 vertices. Proof: Let G be a 3-colored TSC-graph on 2 4 vertices. In this case k = 3, n = 2 4 , p = 2, r = 4. In particular, α : x → x 2 . The cardinality formula yields |A| = (2 4 -1) • 4/ds. Since Aut(G) is arc transitive, (2 4 -1)/3 divides |A|. It follows that ds divides 12. By Lemma 3.3(ii), d divides 2 4 -1 = 15. Hence d = 3. The only possibility for A to have three orbits is e = 0 and s = 2. Since α 2 preserves ω 3 -orbits, this leads to the generalized Paley graph G = GP(2 4 ). The generalized Paley graph GP(2 6 ) is the only 3-colored TSC-graph on 2 6 vertices. Proof: This case is very similar to the previous one. We have k = 3, p = 2, and r = 6. We have |A| = (2 6 -1)•4/ds and (2 6 -1)/3 divides |A|. Whence ds|24. By Lemma 3.3(ii), d divides 2 6 -1 = 63, yielding d = 3. The only possibility for A to have three orbits is e = 0 and s ∈ {2, 4}. The latter, s = 4, is excluded by Lemma 3.3(i), since 4 does not divide r = 6. Hence, A = ω 3 , α 2 , which leads to the generalized Paley graph GP(2 6 ). For each p = 17, 23, 89, the generalized Paley graph GP(p 2 ) is the only 3-colored TSCgraph on p 2 vertices. Proof: Let p ∈ {17, 23, 89}. If s = 2, then A = ω 3 , and the graph is GP(p 2 ), as claimed. The remaining case is s = 1.

2 Lemma 6 . 6

 266 has order 16, and cannot be embedded in ΓL 1 (5 2 ). Obviously, G 3 = G 3 (5 2 ) defined in Section 2. The generalized Paley graph GP(11 2 ) and the graph G 3(11 2 ) introduced in Section 2 are the only two nonisomorphic 3-colored TSC-graphs on 11 2 vertices.

Acknowledgements

We thank Kornel Kisielewicz who helped us to write suitable programs to compute unsettled cases n = 3 4 , 7 4 and 2 8 .