Didier Caucal
email: didier.caucal@univ-mlv.fr

On Cayley graphs of algebraic structures

We present simple graph-theoretic characterizations of Cayley graphs for left-cancellative monoids, groups, left-quasigroups and quasigroups. We show that these characterizations are effective for the end-regular graphs of finite degree.

1

Introduction

To describe the structure of a group, Cayley introduced in 1878 [START_REF] Cayley | The theory of groups: graphical representation[END_REF] the concept of graph for any group (G, •) according to any generating subset S. This is simply the set of labeled oriented edges g s -→ g•s for every g of G and s of S. Such a graph, called Cayley graph, is directed and labeled in S (or an encoding of S by symbols called letters or colors). The study of groups by their Cayley graphs is a main topic of algebraic graph theory [START_REF] Biggs | Algebraic graph theory[END_REF][START_REF] Godsil | Algebraic graph theory[END_REF][START_REF]Topics in algebraic graph theory[END_REF]. A characterization of unlabeled and undirected Cayley graphs was given by Sabidussi in 1958 [START_REF] Sabidussi | On a class of fixed-point-free graphs[END_REF] : an unlabeled and undirected graph is a Cayley graph if and only if we can find a group with a free and transitive action on the graph. However, this algebraic characterization is not well suited for deciding whether a possibly infinite graph is a Cayley graph. It is pertinent to look for characterizations by graph-theoretic conditions. This approach was clearly stated by Hamkins in 2010: Which graphs are Cayley graphs? [START_REF] Hamkins | Which graphs are Cayley graphs?[END_REF]. In this paper, we present simple graph-theoretic characterizations of Cayley graphs for firstly left-cancellative and cancellative monoids, and then for groups. These characterizations are then extended to any subset S of left-cancellative magmas, left-quasigroups, quasigroups, and groups. Finally, we show that these characterizations are effective for the end-regular graphs of finite degree [START_REF] Muller | The theory of ends, pushdown automata, and second-order logic[END_REF] which are the graphs finitely decomposable by distance from a(ny) vertex or equivalently are the suffix transition graphs of labeled word rewriting systems.

Let us present the main structural characterizations starting with the Cayley graphs of left-cancellative monoids. Among many properties of these graphs, we retain only three basic ones. First and by definition, any Cayley graph is deterministic: there are no two arcs of the same source and label. Furthermore, the left-cancellative condition implies that any Cayley graph is simple: there are no two arcs of the same source and goal. Finally, any Cayley graph is rooted: there is a path from the identity element to any vertex. To these three necessary basic conditions is added a structural property, called arc-symmetric: all the vertices are accessible-isomorphic i.e. the induced subgraphs by vertex accessibility are isomorphic. These four properties characterize the Cayley graphs of left-cancellative monoids. To describe exactly the Cayley graphs of cancellative monoids, we just have to add the co-determinism: there are no two arcs of the same target and label. This characterization is strengthened for the Cayley graphs of groups using the same properties but expressed in both arc directions: these are the graphs that are connected, deterministic, co-deterministic, and symmetric: all the vertices are isomorphic.

We also consider the Cayley graph of a magma G according to any subset S and that we called generalized. The characterizations obtained require the assumption of the axiom of choice. First, a graph is a generalized Cayley graph of a left-cancellative magma if and only if it is deterministic, simple, source-complete: for any label of the graph and from any vertex, there is at least one edge. This equivalence does not require the axiom of choice for finitely labeled graphs, and in this case, these graphs are also the generalized Cayley graphs of left-quasigroups. Moreover, a finitely labeled graph is a generalized Cayley graph of a quasigroup if and only if it is also co-deterministic and target-complete: for any label of the graph and to any vertex, there is at least one edge. We also characterize all the generalized Cayley graphs of left-quasigroups, and of quasigroups. Finally, a graph is a generalized Cayley graph of a group if anf only if it is simple, symmetric, deterministic and co-deterministic.

Directed labeled graphs

We consider directed labeled graphs without isolated vertex. We recall some basic concepts such as determinism, completeness and symmetry. We introduce the notions of accessibleisomorphic vertices and arc-symmetric graph.

Let A be an arbitrary (finite or infinite) set. A directed A-graph (V, G) is defined by a set V of vertices and a subset G ⊆ V ×A×V of edges. Any edge (s, a, t) ∈ G is from the source s to the target t with label a, and is also written by the transition s a -→ G t or directly s a -→ t if G is clear from the context. The sources and targets of edges form the set V G of non-isolated vertices of G and we denote by A G the set of edge labels:

V G = { s | ∃ a, t (s a -→ t ∨ t a -→ s) } and A G = { a | ∃ s, t (s a -→ t) }.
Thus V -V G is the set of isolated vertices. From now on, we assume that any graph (V, G) is without isolated vertex (i.e. V = V G ), hence the graph can be identified with its edge set G. We also exclude the empty graph ∅ : every graph is a non-empty set of labeled edges. For instance Υ = { s n -→ s + n | s ∈ R ∧ n ∈ Z } is a graph of vertex set R and of label set Z. As any graph G is a set, there are no two edges with the same source, target and label. We say that a graph is simple if there are no two edges with the same source and target: (s a -→ t ∧ s b -→ t) =⇒ a = b. We say that G is finitely labeled if A G is finite. We denote by G -1 = { (t, a, s) | (s, a, t) ∈ G } the inverse of G. A graph is deterministic if there are no two edges with the same source and label: (r a -→ s ∧ r a -→ t) =⇒ s = t. A graph is codeterministic if its inverse is deterministic: there are no two edges with the same target and label: (s a -→ r ∧ t a -→ r) =⇒ s = t. For instance, the graph Υ is simple, not finitely labeled, deterministic and co-deterministic. A graph G is complete if there is an edge between any couple of vertices: ∀ s, t ∈ V G ∃ a ∈ A G (s a -→ G t). A graph G is source-complete if for all vertex s and label a, there is an a-edge from s :

∀ s ∈ V G ∀ a ∈ A G ∃ t (s a -→ G t). A graph is target-complete if its inverse is source-complete: ∀ t ∈ V G ∀ a ∈ A G ∃ s (s a -→ G t).
For instance, Υ is source-complete, target-complete but not complete. Another example is given by the graph Even = {(p, a, q) , (p, b, p) , (q, a, p) , (q, b, q)} represented as follows:

G |P = { (s, a, t) ∈ G | s, t ∈ P }.
The label-restriction G |P of G to a set P is the subset of all its edges labeled in P :

G |P = { (s, a, t) ∈ G | a ∈ P }.
Let -→ G be the unlabeled edge relation i.e. s -→ G t if s a -→ G t for some a ∈ A. We D. Caucal XX:3 denote by -→ G (s) = { t | s -→ G t } the set of successors of s ∈ V G . We write s / -→ G t if there is no edge in G from s to t i.e. G ∩ {s}×A×{t} = ∅. The accessibility relation

-→ * G = n≥0 -→ n G is the reflexive and transitive closure under composition of -→ G . A graph G is accessible from P ⊆ V G if for any s ∈ V G , there is r ∈ P such that r -→ * G s.
We denote by G ↓P the induced subgraph of G to the vertices accessible from P which is the greatest subgraph of G accessible from P . For instance

Υ ↓{0} = { m n -→ m+n | m, n ∈ Z } is a complete subgraph of Υ. A root r is a vertex from which G is accessible i.e. G ↓{r} also denoted by G ↓r is equal to G. A graph G is strongly connected if every vertex is a root: s -→ * G t for all s, t ∈ V G . A graph G is co-accessible from P ⊆ V G if G -1 is accessible from P . We denote by d G (s, t) = min{ n | s -→ n G ∪ G -1 t } the distance between s, t ∈ V G with min(∅) = ω. A graph G is connected if G ∪ G -1 is strongly connected i.e. d G (s, t) ∈ N for any s, t ∈ V G . Recall that a connected component of a graph G is a maximal connected subset of G ; we denote by Comp(G) the set of connected components of G. A representative set of Comp(G) is a vertex subset P ⊆ V G having exactly one vertex in each connected component: |P ∩ V C | = 1 for any C ∈ Comp(G)
; it induces the canonical mapping π P : V G -→ P associating with each vertex s the vertex of P in the same connected component:

s -→ * G ∪ G -1 π P (s) for any s ∈ V G . For instance, [0, 1[ is a representative set of Comp(Υ) and its canonical mapping is defined by π [0,1[ (x) = x -⌊x⌋ for any x ∈ R. A path (s 0 , a 1 , s 1 , . . . , a n , s n ) of length n ≥ 0 in a graph G is a sequence s 0 a1 -→ s 1 . . . an -→ s n
of n consecutive edges, and we write s 0 a1...an -→ s n for indicating the source s 0 , the target s n and the label word a 1 . . .a n ∈ A * G of the path where A * G is the set of words over A G (the free monoid generated by A G ) and ε is the empty word (the identity element). Recall that a morphism from a graph G into a graph H is a mapping

h from V G into V H such that s a -→ G t =⇒ h(s) a -→ H h(t).
If, in addition h is bijective and h -1 is a morphism, h is called an isomorphism from G to H ; we write G ≡ h H or directly G ≡ H if we do not specify an isomorphism, and we say that G and H are isomorphic. An automorphism of G is an isomorphism from G to G. Two vertices s, t of a graph G are isomorphic and we write s ≃ G t if t = h(s) for some automorphism h of G. A graph G is symmetric (or vertex-transitive) if all its vertices are isomorphic: s ≃ G t for every s, t ∈ V G . For instance, the previous graphs Υ and Even are symmetric. Two vertices s, t of a graph G are accessible-isomorphic and we write s ↓ G t if t = h(s) for some isomorphism h from G ↓s to G ↓t . A graph G is arc-symmetric if all its vertices are accessible-isomorphic: s ↓ G t for every s, t ∈ V G .

◮ Fact 1. Any symmetric graph is arc-symmetric which is source-complete.

For instance Υ

|{1} |IN = { n 1 -→ n + 1 | n ∈ N } is arc-symmetric but not symmetric. On the other hand Υ |{-1} |IN = { n -1 -→ n -1 | n ∈ N } is not arc-symmetric: two distinct vertices are not accessible-isomorphic.

Cayley graphs of left-cancellative and cancellative monoids

We present graph-theoretic characterizations for the Cayley graphs of left-cancellative monoids (Theorem 7), of cancellative monoids (Theorem 8), of cancellative semigroups (Theorem 10).

A magma (or groupoid) is a set M equipped with a binary operation • : M ×M -→ M that sends any two elements p, q ∈ M to the element p • q. Given a subset Q ⊆ M and an injective mapping [ [ ]

] : Q -→ A, we define the graph C[ [M, Q] ] = { p [[q]] -→ p • q | p ∈ M ∧ q ∈ Q } which is called a generalized Cayley graph of M . It is of vertex set M and of label set [ [Q] ] = { [ [q] ] | q ∈ Q }. We denote C[ [M, Q] ] by C(M, Q) when [ [ ] ] is the identity. For instance Υ = C(R, Z) for the magma (R, +). We also write C[ [M ] ] instead of C[ [M, M ] ] and C(M ) = C(M, M ) = { p q -→ p • q | p, q ∈ M }.
◮ Fact 2. Any generalized Cayley graph is deterministic and source-complete.

For instance taking the magma (Z, -) and [

[-1] ] = a, C[ [Z, {-1}] ] = { n a -→ n + 1 | n ∈ Z }. By adding [ [1] ] = b, C[ [Z, {1, -1}] ] = { n a -→ n + 1 | n ∈ Z } ∪ { n b -→ n -1 | n ∈ Z }. We say that a magma (M, •) is left-cancellative if r •p = r •q =⇒ p = q for any p, q, r ∈ M . Similarly (M, •) is right-cancellative if p • r = q • r =⇒ p = q for any p, q, r ∈ M .
A magma is cancellative if it is both left-cancellative and right-cancellative.

◮ Fact 3. Any generalized Cayley graph of a left-cancellative magma is simple.

Any generalized Cayley graph of a right-cancellative magma is co-deterministic.

Recall also that (M,

•) is a semigroup if • is associative: (p • q) • r = p • (q • r) for any p, q, r ∈ M . A monoid (M, •) is a semigroup with an identity element 1 : 1•p = p•1 = p for all p ∈ M . The submonoid generated by Q ⊆ M is the least submonoid Q * = { q 1 • . . . •q n | n ≥ 0 ∧ q 1 , . . . , q n ∈ Q } containing Q.
When a monoid is left-cancellative, its generalized Cayley graphs are arc-symmetric.

◮ Proposition 4. Any generalized Cayley graph of a left-cancellative monoid is arc-symmetric.

Proof.

Let G = C[ [M, Q] ] for some left-cancellative monoid (M, •) and some Q ⊆ M .
Let r ∈ M . We have to check that 1 ↓ G r. By induction on n ≥ 0 and for any q 1 , . . . , q n ∈ Q and s ∈ M , we have r

[ [q 1 ]]...[ [qn]] -→ G s ⇐⇒ s = (. . .(r•q 1 ). . .)•q n . As • is associative, we get V G ↓r = { s | r -→ * G s } = r•Q * . In particular V G ↓1 = Q * . We consider the mapping f r : M -→ M defined by f r (p) = r•p for any p ∈ M . As • is left-cancellative, f r is injective. Furthermore f r is an isomorphism on its image: for any p, q, p ′ ∈ M , p [ [q]] -→ G p ′ ⇐⇒ f r (p) [ [q]] -→ G f r (p ′ ).
The associativity of • gives the necessary condition. The associativity and the left-cancellative property of • gives the sufficient condition.

Thus f r restricted to Q * is an isomorphism from G ↓1 to G ↓r hence 1 ↓ G r. ◭
We can not generalize Proposition 4 to the left-cancellative semigroups. For instance the semigroup M = {a, b} with x•y = y for any x, y ∈ M is left-cancellative but the graph

C(M ) represented below is not arc-symmetric. a a b b a b A monoid Cayley graph is a generalized Cayley graph C[ [M, Q] ] of a monoid M generated by Q which means that the identity element 1 is a root of C[ [M, Q] ]. ◮ Fact 5. A monoid M is generated by Q ⇐⇒ 1 is a root of C[ [M, Q] ].

D. Caucal

XX:5

Under additional simple conditions, let us establish the converse of Proposition 4. For any graph G and any vertex r, we introduce the path-relation Path G (r) as the ternary relation on V G defined by (s, t, x) ∈ Path G (r) if there exists u ∈ A * G such that r u -→ G t and s u -→ G x. If for any s, t ∈ V G there exists a unique x such that (s, t, x) ∈ Path G (r), we denote by * r : V G ×V G -→ V G the binary path-operation on V G defined by (s, t, s * r t) ∈ Path G (r) for any s, t ∈ V G ; we also write G * r when we need to specify G. Let us give conditions so that this path-operation exists and is associative and left-cancellative.

◮ Proposition 6. Let r be a root of a deterministic and arc-symmetric graph G.

Then (V G , * r ) is a left-cancellative monoid of identity r and generated by -→ G (r). If G is co-deterministic then * r is cancellative. If G is simple then G = C[ [V G , -→ G (r)] ] with [ [s] ] = a for any r a -→ G s. Proof. i) Let s, t ∈ V G .
Let us check that there is a unique x such that (s, t, x) ∈ Path G (r). As r is a root, there exists u such that r

u -→ G t. As G is source-complete, there exists x such that s u -→ G x. Hence (s, t, x) ∈ Path G (r). Let (s, t, y) ∈ Path G (r). There exists v ∈ A * G such that r v -→ G t and s v -→ G y. As G is arc-symmetric, we have r ↓ G s and as G is deterministic, we get s v -→ G x.
As G is deterministic, it follows that x = y. Thus * r exists and is denoted by • in the rest of this proof. Let us show that (V G , •) is a left-cancellative monoid.

ii) Let us show that • is associative. Let x, y, z ∈ V G . We have to check that (x•y)•z = x•(y•z). As r is a root, there exists v, w ∈ A * G such that r v -→ y and r w -→ z.

By (i), x v -→ x•y w -→ (x•y)•z and y w -→ y•z So r vw -→ y•z hence x vw -→ x•(y•z). As G is deterministic, we get (x•y)•z = x•(y•z). iii) Let us check that r is an identity element. Let s ∈ V G . As r ε -→ r, we get s ε -→ s•r i.e. s•r = s. For r u -→ s, we have r u -→ r•s. As G is deterministic, we get r•s = s. iv) Let us check that • is left-cancellative. Let s, t, t ′ ∈ V G such that s•t = s•t ′ . There exists u, v ∈ A * G such that r u -→ t and r v -→ t ′ . So s u -→ s•t and s v -→ s•t ′ . As s•t = s•t ′ and r ↓ G s, we get r v -→ t. As G is deterministic, we have t = t ′ . v) Let us check that Q = -→ G (r) is a generating subset of V G . Let s ∈ V G . There exists n ≥ 0, a 1 , . . . , a n ∈ A G and s 0 , . . . , s n such that r = s 0 a1 -→ s 1 . . .s n-1 a1 -→ s n = s. By Fact 1, there exists r 1 , . . . , r n such that r a1 -→ r 1 , . . . , r an -→ r n . For every 1 ≤ i ≤ n, s i = s i-1 •r i hence s = r•r 1 • . . . •r n = r 1 • . . . •r n ∈ Q * . vi) Assume that G is co-deterministic. Let us check that • is right-cancellative. Let s, s ′ , t ∈ V G such that s•t = s ′ •t. There exists u ∈ A * G such that r u -→ t. So s u -→ s•t and s ′ u -→ s ′ •t = s•t. As G is co-deterministic, we get s = s ′ . vii) Assume that G is simple. Let Q = { s | r -→ G s }.
As G is simple and deterministic, we define the following injection

[ [ ] ] from Q into A G by XX:6
Cayley graphs It is a skeleton of the graph of ω 2 where a is the successor and b goes to the next limit ordinal: (V G , -→ * G ) is isomorphic to (ω 2 , ≤). By Proposition 6, it is a Cayley graph of a left-cancellative monoid. Precisely to each word u ∈ b * a * , we associate the unique vertex <u> ∈ V G accessible from the root by the path labeled by u. Thus

[ [s] ] = a for r a -→ G s. Let K = C[ [V G , Q] ]. Let us show that G = K. ⊆ : Let s a -→ G t. As r ↓ G s, there exists r ′ such that r a -→ G r ′ . So s a -→ G s•r ′ . As G is deterministic, s•r ′ = t. Furthermore r ′ ∈ Q and [ [r ′ ] ] = a. So s a -→ K s•r ′ = t. ⊇ : Let s a -→ K t. So a = [ [r ′ ] ] for some r ′ ∈ Q. Thus t = s•r ′ and r a -→ G r ′ . So s a -→ G s•r ′ = t. ◭
G = { <b m a n > a -→ <b m a n+1 > | m, n ≥ 0 } ∪ { <b m a n > b -→ <b m+1 > | m, n ≥ 0 }.
By Proposition 6, (V G , * <ε> ) is a left-cancellative monoid where for any m, n, p, q ≥ 0,

<b m a n > * <ε> <b p a q > = <b m a n+q > if p = 0 <b m+p a q > if p = 0

◮ Theorem 7. A graph is a Cayley graph of a left-cancellative monoid if and only if

it is rooted, simple, deterministic and arc-symmetric.

Proof.

We obtain the necessary condition by Proposition 4 with Facts 2,3,5.

The sufficient condition is given by Proposition 6. ◭

We can restrict Theorem 7 to cancellative monoids.

◮
[ [M, Q] ] such that M = Q + whose Q + = { q 1 • . . . •q n | n > 0 ∧ q 1 , . . . , q n ∈ Q } is

Proof.

Let M = M ∪ {1} be a monoid-completion of a cancellative semigroup M without an identity element. ii) By hypothesis M has no identity element. By (i), there are no m, e ∈ M such that

m•e = m. Let us show that M is left-cancellative. Let m•p = m•q for some m, p, q ∈ M . Let us check that p = q.
As M is left-cancellative, we only have to consider the case where 1 ∈ {m, p, q}.

If m = 1 then p = 1•p = 1•q = q.
Otherwise m ∈ M and 1 ∈ {p, q}. By (i), we get p = q = 1.

iii) Similarly there are no m, e ∈ M such that e•m = m hence M remains also rightcancellative. ◭

Let us translate the monoid-completion of cancellative semigroups into their Cayley graphs. is arc-symmetric but is not rootable into an arc-symmetric graph. On the other hand, a graph consisting of two (isomorphic) deterministic and source-complete trees over {a, b} is rootable into a deterministic source-complete tree over {a, b}. Finally the following graph: is also rootable into a simple, deterministic, co-deterministic, arc-symmetric graph. We can apply Theorem 8.

A root-completion of a graph G is a graph G defined by G = G if G is rooted, otherwise G ⊂ G ⊆ G ∪ {r}×A G ×V G and

◮ Theorem 10. A graph is a Cayley graph of a cancellative semigroup if and only if

it is rootable into a simple, deterministic, co-deterministic, arc-symmetric graph.

Proof. =⇒ : Let

G = C[ [M, Q] ]
for some cancellative semigroup M and some generating subset Q of M i.e. Q + = M . We have the following two complementary cases.

Case 1 : M has an identity element. By Theorem 8, G is rooted, simple, arc-symmetric, deterministic and co-deterministic. As G has a root, it is rootable into itself.

Case 2 : M is not a monoid. Let M = M ∪ {1} be a monoid-completion of M . By Lemma 9, ,M remains cancellative. Furthermore

Q * = M . Let G = C[ [M , Q] ] = G ∪ { 1 [ [q]] -→ q | q ∈ Q }. By Theorem 8, G is rooted, simple, arc-symmetric, deterministic and co-deterministic. Moreover G is rootable into G.
⇐= : Let a graph G rootable into a simple, deterministic, co-deterministic, arc-symmetric graph G. We have the following two complementary cases. Case 1 : G is rooted. By Theorem 8 (or Proposition 6), G is a Cayley graph of a cancellative monoid. Case 2 : G has no root. Let r be the root of G and

Q = -→ G (r). So Q ⊆ V G and V G = V G -{r}. By Proposition 6, G = C[ [V G , Q] ]
for the associative and cancellative path-operation * r on V G of identity element r with V G generated by Q. As r is not the target of an edge of G and by definition, * r remains an internal operation on

V G i.e. p * r q = r for any p, q ∈ V G . Finally G = C[ [V G , Q] ] and (V G , * r ) is a cancellative semigroup. ◭
For instance by Theorem 10, the previous graph is a Cayley graph of a cancellative semigroup. It is isomorphic to We can now restrict Theorem 8 to the Cayley graphs of groups.

D. Caucal XX:9 G = { n a -→ n + 1 | n > 0 } ∪ { n a -→ n -1 | n < 0 } ∪ { n b -→ -n -1 | n > 0 } ∪ { n b -→ -n + 1 | n < 0 }. We have G = C[ [Z -{0} , {-1, 1}] ] with [ [1] ] = a

Cayley graphs of groups

We present a graph-theoretic characterization for the Cayley graphs of groups: they are the deterministic, co-deterministic, symmetric, simple and connected graphs (Theorem 17). By removing the connectivity condition and under the assumption of the axiom of choice, we get a characterization for the generalized Cayley graphs of groups (Theorem 20).

Recall that a group (M, •) is a monoid whose each element p ∈ M has an inverse p -1 :

p•p -1 = 1 = p -1 •p. So C(M ) is strongly connected hence by Proposition 4 is symmetric.
◮ Fact 11. Any generalized Cayley graph of a group is symmetric.

Proof. Let (M, •) be a group and [ [ ] ] : M

-→ A be an injective mapping. By Proposition 4, C[ [M ] ] is arc-symmetric. As C[ [M ] ] is strongly connected, C[ [M ] ] is symmetric. For any Q ⊆ M , C[ [M, Q] ] = C[ [M ] ] |[ [Q]] remains symmetric. ◭
We start by considering the monoid Cayley graphs of a group M which are the generalized

Cayley graph C[ [M, Q] ] with Q * = M .
◮ Fact 12. Any monoid Cayley graph of a group is strongly connected.

Proof.

Let G = C[ [M, Q] ] for some group M and some Q ⊆ M with Q * = M . Let p ∈ M . We have to check that 1 -→ * G p -→ * G 1. There exists n ≥ 0 and q 1 , . . . , q n ∈ Q such that p = q 1 • . . . •q n . So 1 [ [q 1 ]]...[ [qn ]] -→ G p. For any 1 ≤ i ≤ n, we have q -1 i = q i,1 • . . . •q i,mi for some m i ≥ 0 and q i,1 , . . . , q i,mi ∈ Q. Thus p u -→ G 1 for u = [ [q n,1 ] ]. . .[ [q n,mn ] ] . . . [ [q 1,1 ] ]. . .[ [q 1,m1 ] ]. ◭
Let us complete Proposition 6 in the case where the graph is symmetric. In this case, the path-operation is also invertible.

◮ Proposition 13. For any root r of a deterministic and symmetric graph G, (V G , * r ) is a group.

Proof.

It suffices to complete the proof of Proposition 6 when G is in addition symmetric.

Let s ∈ V G . Let us show that s has an inverse. There exists

u ∈ A * G such that r u -→ s. As r ≃ G s, s is also a root hence there exists v such that s v -→ r. Let s be the vertex such that r v -→ s. So s u -→ s•s and s v -→ s•s. As G is deterministic, we get s•s = r. As r ≃ G s and s vu -→ s, we get r vu -→ r. As G is deterministic, we get s u -→ r hence s•s = r. ◭
We describe the monoid Cayley graphs of groups from the characterization of the Cayley graphs of left-cancellative monoids (Theorem 7) just by replacing the arc-symmetry by the symmetry.

◮ Theorem 14. A graph is a monoid Cayley graph of a group if and only if it is rooted, simple, deterministic and symmetric.

Proof.

=⇒ : By Theorem 7 and Fact 11.

⇐= : By Propositions 6 and 13. ◭

For instance by Theorem 14, a graph of the following representation: From Fact 12, we can replace in Theorem 14 the rooted condition by the fact to be strongly connected. By Fact 3, we can also add the co-determinism condition.

◮ Corollary 15. Any rooted, simple, deterministic and symmetric graph is strongly connected and co-deterministic.

We can now consider a group Cayley graph as a generalized Cayley graph

C[ [M, Q] ] such that M is a group equal to the subgroup generated by Q which is the least subgroup (Q ∪ Q -1 ) * containing Q where Q -1 = { q -1 | q ∈ Q } is the set of inverses of the elements in Q. For instance, the a-line { n a -→ n + 1 | n ∈ Z } is the Cayley graph C[ [Z, {1}] ] of the group (Z, +) with [ [1] ] = a
. This unrooted graph is not a monoid Cayley graph. Let us generalize Theorem 14 to these well-known Cayley graphs. We need to be able to circulate in a graph in the direct and inverse direction of the arrows. Let G be a graph and let -:

A G -→ A -A G be an injective mapping of image A G = { a | a ∈ A G }. A chain s u -→ G t is a path labeled by u ∈ (A G ∪ A G ) * where for any a ∈ A G , we have s a -→ G t for t a -→ G s. Given a vertex r, the path-relation Path G (r) is extended into the chain-relation Chain G (r) as the ternary relation on V G defined by (s, t, x) ∈ Chain G (r) if there exists u ∈ (A G ∪ A G ) * such that r u -→ G t and s u -→ G x. Thus Path G (r) ⊆ Chain G (r) = Path G (r) for G = G ∪ { t a -→ s | s a -→ G t }. If for any s, t ∈ V G there exists a unique x such that (s, t, x) ∈ Chain G (r), we denote by * r : V G ×V G -→ V G the binary chain-operation on V G defined by (s, t, s * r t) ∈ Chain G (r)
for any s, t ∈ V G ; we also write G * r when we need to specify G. Let us adapt Propositions 6 and 13 to this chain-operation.

◮ Proposition 16. Let r be a vertex of a connected, symmetric, deterministic and co-deterministic graph G.

D. Caucal

XX:11

Then (V G , * r ) is a group of identity r generated by -→ G (r). If G is simple then G = C[ [V G , -→ G (r)] ] with [ [s] ] = a for any r a -→ G s.

Proof.

i) The graph G remains symmetric. As G is deterministic and co-deterministic, G is deterministic. As G is connected, G is strongly connected. By applying Propositions 6 and 13 to G, we get that (V G , * r ) is a group of identity r and

V G = V G = (-→ G (r)) * with -→ G (r) = -→ G (r) ∪ -→ G -1 (r). ii) Let us check that -→ G -1 (r) = (-→ G (r)) -1 . ⊆ : Let s ∈ -→ G -1 (r) i.e. r -→ G -1 s. So s a -→ G r for some a ∈ A. As G is source-complete, there exists t such that r a -→ G t. Thus s a -→ G s * r t. As G is deterministic, s * r t = r hence s = t -1 ∈ (-→ G (r)) -1 . ⊇ : Let s ∈ (-→ G (r)) -1 i.e. r a -→ G s -1 for some a ∈ A. So s a -→ G s * r s -1 = r i.e. s ∈ -→ G -1 (r).
iii) Suppose that in addition G is simple. Note that G can be not simple. Thus we define the graph

G = G ∪ { t a -→ s | s a -→ G t / -→ G s }. Let us show that G * r = G * r . As G ⊆ G, we get G * r ⊆ G * r = G * r .
Let us show the inverse inclusion. We consider the mapping π :

A G ∪ A G -→ A G defined for any a ∈ A G by π(a) = a, and for any a ∈ A G -A G , π(a) is the unique letter in A G such that t π(a)
-→ G s for any s a -→ G t. This makes sense because G is deterministic, co-deterministic and symmetric. Thus

s a -→ G t =⇒ s π(a) -→ G t for any a ∈ A G ∪ A G .

By extending π by morphism on (A

G ∪ A G ) * , we get s u -→ G t =⇒ s π(u) -→ G t for any u ∈ (A G ∪ A G ) * . This implies that G * r ⊆ G * r .
iv) Having G simple, symmetric, deterministic and co-deterministic, G remains simple, symmetric, deterministic, and is strongly connected. By Proposition 6, Proof.

G = C[ [V G , -→ G (r)] ] with [ [s] ] = a for any r a -→ G s. Precisely for any s ∈ -→ G (r), we have [ [s] ] = a if r a -→G s a if s a -→G r / -→G s. Thus G = G |AG = C[ [V G , -→ G (r)] ]. ◭
=⇒ : Let G = C[ [M, Q] ] for some group M and Q ⊆ M with (Q ∪ Q -1 ) * = M .
By Facts 2, 3, 11, G is simple, symmetric, deterministic and co-deterministic. By Fact 12, the monoid Cayley graph

C[ [M, Q ∪ Q -1 ] ] is strongly connected. Thus G = C[ [M, Q ∪ Q -1 ] ] |[ [Q]] is
(P ) if there exists u, v ∈ (A G ∪ A G ) * such that π P (s) u -→ G s and π P (t) v -→ G t and π P (s) • π P (t) uv -→ G x.
For any connected and deterministic graph G and any vertex r, Chain G ({r}) = Chain G (r). If for any s, t ∈ V G there exists a unique x such that (s, t, x) ∈ Chain G (P ), we denote by

* P : V G ×V G -→ V G the
∪ -→ G (r). If G is simple then G = C[ [V G , -→ G (r)] ] with [ [s] ] = a for any r a -→ G s.
Proof. i) Let (P, •) be a group generated by P 0 of identity r. Let C ∈ Comp(G) with r ∈ V C . By Proposition 16, (V C , * r ) is a group of identity r and is generated by -→ G (r). We take the group product (P ×V C , •) with (p, x) • (q, y) = (p • q, x * r y) for any p, q ∈ P and x, y ∈ V C . This group is of identity (r, r) and is generated by

P 0 ×{r} ∪ {r}×-→ G (r).
As G is symmetric, deterministic and co-deterministic, we can define the mapping f :

P ×V C -→ V G such that r u -→ G x =⇒ p u -→ G f (p, x) for (any) u ∈ (A G ∪ A G ) * . Thus f is a bijection hence (V G , •) is a group where f (p, x) • f (q, y) = f (p • q, x * r y) for any p, q ∈ P and x, y ∈ V C . This group (V G , •) is of identity f (r, r) = r and is generated by f (P 0 ×{r}) ∪ f ({r}×-→ G (r)) = P 0 ∪ -→ G (r).
ii) Let us show that the operation • on V G is equal to * P . Let p, q ∈ P and x, y ∈ V C . We have to check that f (p, x)

* P f (q, y) = f (p, x) • f (q, y). Let u, v ∈ (A G ∪ A G ) * such that r u -→ G x and r v -→ G y. By definition of * P , we have x v -→ G x * r y hence r uv -→ G x * r y. By definition of f , we get p • q uv -→ G f (p • q, x * r y), p u -→ G f (p, x) and q v -→ G f (q, y). By definition of * P , we have p • q uv -→ G f (p, x) * P f (q, y). As G is deterministic, we get f (p, x) * P f (q, y) = f (p • q, x * r y) = f (p, x) • f (q, y). D. Caucal XX:13 iii) Suppose that in addition G is simple. Let [ [y] ] = a for any r a -→ G y. Thus C[ [VG, -→G(r)] ] = { s a -→ s • y | s ∈ VG ∧ r a -→ y } = { s a -→ s * P y | s ∈ VG ∧ r a -→ y } = G.

◭

In ZF set theory, the axiom of choice is equivalent to the property that any non-empty set has a group structure [START_REF] Hajnal | Some new algebraic equivalents of the axiom of choice[END_REF]. Under the assumption of the axiom of choice, we can characterize the generalized Cayley graphs of groups.

◮ Theorem 20. In ZFC set theory, a graph is a generalized Cayley graph of a group if and only if it is simple, deterministic, co-deterministic, symmetric.

Proof.

By Facts 2, 3, 11, any generalized Cayley graph is symmetric, deterministic and co-deterministic. Conversely let G be a simple, deterministic, co-deterministic, symmetric graph. Using ZFC set theory, there exists a representative set P of comp(G) and a binary operation • such that (P, •) is a group. By Proposition 19, (V G , * P ) is a group and

G = C[ [V G , -→ G (r)] ] with [ [s] ] = a for any r a -→ G s. ◭
For instance let us consider the following graph:

G = { (m, i, p) a -→ (m + 1, i, p) | m, p ∈ Z ∧ i ∈ {0, 1} } ∪ { (m, i, p) b -→ (m, 1 -i, p) | m, p ∈ Z ∧ i ∈ {0, 1} }
of representation the countable repetition of the preceding one. By Theorem 20,

G = C[ [Z×{0, 1}×Z, {(1, 0, 0), (0, 1, 0)}] ] with [ [(1, 0, 0)] ] = a, [ [(0, 1, 0)] ] = b and for the group operation (m, i, p) • (n, j, q) = (m + n, i + j (mod2), p + q).
Let us summarize the characterizations obtained for the Cayley graphs of monoids.

Cancellative monoids + co-deterministic (8)

Groups

Left-cancellative monoids + symmetric [START_REF] Läuchli | Monadic second order definable relations on the binary tree[END_REF] rooted + simple + deterministic + arc-symmetric [START_REF]On the regular structure of prefix rewriting[END_REF] By relaxing the condition of being rooted by that of connectivity, we have obtained a graphtheoretic characterization for the Cayley graphs of groups (Theorem 17).

Generalized Cayley graphs of left-cancellative magmas

Under ZFC set theory, we will give a fully graph-theoretic characterization for generalized Cayley graphs of left-cancellative magmas (Theorem 25), and then when they have an identity (Theorem 27).

Recall that an element e of a magma (M, •) is a left identity (resp. right identity) if e•p = p (resp. p•e = p) for any p ∈ M . If M has a left identity e and a right identity e ′ then e = e ′ which is an identity (or neutral element) of M . In order to characterize the Cayley graphs of left-cancellative magmas with or without an identity, we need to restrict the path-relation. For any graph G and any vertex r, we define the edge-relation Edge G (r) as the ternary relation on V G defined by

(s, t, x) ∈ Edge G (r) if there exists a ∈ A G such that r a -→ G t and s a -→ G x.

XX:14 Cayley graphs

So Edge G (r) ⊆ Path G (r). If for any s, t ∈ V G there exists a unique x such that (s, t, x) ∈ Edge G (r), we denote by × r : V G ×V G -→ V G the binary edge-operation on V G defined by (s, t, s × r t) ∈ Edge G (r) for any s, t ∈ V G ; we also write G × r when we need to specify G. Let us give conditions for the existence of this edge-operation. We need to introduce two basic graph notions. We say that a vertex r of a graph G is an 1-root if r -→ G s for any vertex s of G. Thus a graph is complete if and only if all its vertices are 1-roots.

◮ Fact 21. Any left identity of a magma M is an 1-root of C(M ).

Moreover we say that a graph is loop-complete if one vertex has an a-loop then all the vertices have an a-loop:

∃ r ∈ V G (r a -→ G r) =⇒ ∀ s ∈ V G (s a -→ G s).
◮ Fact 22. Any generalized Cayley graph of a left-cancellative magma with a right identity is loop-complete.

Proof.

Let M be a left-cancellative magma with a right-identity e.

Let G = C[ [M, Q] ] be a generalized Cayley graph of M . Let p [ [q]]
-→ G p for some p ∈ M and q ∈ Q. So p•q = p = p•e. As M is left-cancellative, q = e. Thus r

[ [q]] -→ G r•q = r•e = r for any r ∈ M . ◭
Let us adapt Propositions 6 to the edge-operation.

◮ Proposition 23. Let r be an 1-root of a deterministic source-complete simple graph G.

Then (V G , × r ) is a left-cancellative magma of left-identity r and G = C[ [V G ] ] with [ [s] ] = a for any r a -→ G s. If G is loop-complete then r is an identity. Proof. i) Let s, t ∈ V G .
Let us check that there is a unique x such that (s, t, x) ∈ Edge G (r). As r is an 1-root and G is simple, there exists a unique a ∈ A G such that r a -→ G t. As G is source-complete and deterministic, there exists a unique vertex x such that s a -→ G x. Thus × r exists and is denoted by • in the rest of this proof.

ii) Let us check that (V G , •) is left-cancellative. Assume that s•t = s•t ′ .
As r is an 1-root, there exists a, a

′ ∈ A G such that r a -→ G t and r a ′ -→ G t ′ . By definition of • we get s a -→ G s • t and s a ′ -→ G s•t ′ = s•t. As G is simple, we have a = a ′ . As G is deterministic, it follows that t = t ′ . iii) Let us check that r is a left identity of (V G , •). Let s ∈ V G . As r is an 1-root, there exists a ∈ A G such that r a -→ G s. By definition of • we have r a -→ G r•s. As G is deterministic, we get r•s = s. iv) As r is an 1-root and G is simple, we can define the mapping [ [ ] ] : V G -→ A G by [ [s] ] = a for r a -→ G s. As G is deterministic, [ [ ] ] is an injection. As G is source-complete, [ [ ] ] is a bijection. Let us show that G = C[ [V G ] ]. ⊆ : Let s a -→ G t. As G is source-complete, there exists r ′ such that r a -→ G r ′ . So s a -→ G s•r ′ . As G is deterministic, s•r ′ = t. We have [ [r ′ ] ] = a hence s a -→ C[ [V G ]] s•r ′ = t. ⊇ : Let s a -→ C[ [V G ]] t. There exists (a unique) r ′ ∈ V G such that [ [r ′ ] ] = a. Thus t = s•r ′ and r a -→ G r ′ . So s a -→ G s•r ′ = t.

D. Caucal

XX:15

v) Assume that G is loop-complete. Let us check that r is also a right identity. As r is an 1-root, there is (a unique)

a ∈ A G such that r a -→ G r. Let s ∈ V G . As G is loop-complete, we get s a -→ G s. By definition of • we have s a -→ s•r. As G is deterministic, s = s•
V G --→ G (r) = { s ∈ V G | r / -→ G
s } of minimal cardinality. For each vertex s, we take an injection f s from V G --→ G (r) to V G --→ G (s) and whose f r is the identity. We define the graph

<G> = { s p -→ t | ∃ a (s a -→ G t ∧ r a -→ G p) } ∪ { s t -→ f s (t) | s ∈ V G ∧ t ∈ Dom(f s ) }.
Thus <G> remains simple, deterministic, source-complete with

V <G> = V G = A <G> . Furthermore r s -→ <G> s for any s ∈ V G hence r is an 1-root of <G>. By Proposition 23, <G> = C(V G ) for (V G , × r ) left-cancellative, of left identity r with s t -→ <G> s × r t for any s, t ∈ V G . Finally G = C[ [V G , -→ G (r)] ] with [ [s] ] = a for any r a -→ G s. ◭ For instance, let G = { m 0 -→ 0 | m ≥ 0 } ∪ { m 1 -→ m + 1 | m ≥ 0 } represented by 0 0 1 1
It is simple, deterministic, source-complete but not loop-complete. By Theorem 25, this graph is a generalized Cayley graph of a left-cancellative magma with a left identity. Precisely we complete G into the graph

<G> = { m 0 -→ 0 | m ≥ 0 } ∪ { m n -→ m + n | m ≥ 0 ∧ n >
0 } having 0 as 1-root, and which remains simple, deterministic, source-complete.

XX:16 Cayley graphs

By Proposition 23, the magma (N, × 0 ) with the edge-operation × 0 of <G> i.e. m × 0 0 = 0 and m × 0 n = m + n for any m ≥ 0 and n > 0 is left-cancellative and 0 is a left identity. Furthermore G = C(N, {0, 1}).

We can now characterize the generalized Cayley graphs of the left-cancellative magmas with an identity. We just have to add the loop-complete property to restrict Proposition 24 to left-cancellative magmas with an identity element.

◮ Proposition 26. A graph is equal to C[ [M ]

] for some left-cancellative magma M with an identity if and only if it is simple, deterministic, source-complete, loop-complete and 1-rooted. Let us apply the construction given in the proof of Theorem 25. As G is loop-complete and if r / -→ G r, we can add the condition that f s (r) = s for any s ∈ V G . Thus <G> remains loop-complete and by Proposition 23, r is an identity for × r . ◭

For instance, we denote by N + = N -{0} and we consider the graph

G = { 0 n 0 -→ 0 n+1 | n ≥ 0 } ∪ { ui 0 -→ u | u ∈ 0 * N + * ∧ i ∈ N + }.
of vertex set V G = 0 * N + * and represented as follows:

0 0 0 0 0 0 0 0 0 0
It is simple, deterministic, source-complete and loop-complete (and arc-symmetric). By Theorem 27, this graph is a generalized Cayley graph of a left-cancellative magma having an identity. For instance, we complete G into the graph

<G> = G ∪ { 0 m u 0 n v -→ 0 m+n uv | m, n ≥ 0 ∧ u, v ∈ N + * ∧ 0 n v = 0 }
which remains simple, deterministic, source-complete, loop-complete, with the 1-root ε. By Proposition 23, G = C(V G , {0}) for the left-cancellative magma (V G , × ε ) of identity ε with the edge-operation × ε of <G> defined for any m, n ≥ 0, u, v ∈ N + * and i ∈ N + by 0 m ui × ε 0 = 0 m u otherwise 0 m u × ε 0 n v = 0 m+n uv.

D. Caucal

XX:17

We will see that we can define <G> so that in addition, any vertex is an 1-root i.e. <G> is complete (see Theorem 33).

Generalized Cayley graphs of left-quasigroups

We can now refine the previous characterization of generalized Cayley graphs from leftcancellative magmas to left-quasigroups (Theorem 32). These algebraic structures define the same family of finitely labeled generalized Cayley graphs (Theorem 33).

A magma (M, •) is a left-quasigroup if for each p, q ∈ M, there is a unique r ∈ M such that p•r = q denoted by r = p\q the left quotient of q by p. This property ensures that each element of M occurs exactly once in each row of the Cayley table for • . For instance {a, b, c} is a left-quasigroup for • defined by the following Cayley table: Let us refine Proposition 23 in the case where the graph is also complete.

◮ Proposition 28. Let G be a simple, deterministic, complete and source-complete graph. For any vertex r, (V G , × r ) is a left-quasigroup.

Proof.

Let r be a vertex of G. As G is complete, r is an 1-root. By Proposition 23, (

V G , × r ) is a left-cancellative magma. Let s ∈ V G . It remains to check that V G ⊆ s × r V G . Let t ∈ V G . As G is complete, there exists a ∈ A G such that s a -→ G t. As G is source-complete, there exists t ′ ∈ V G such that r a -→ G t ′ . By definition of × r we have s a -→ G s × r t ′ . As G is deterministic, we get t = s × r t ′ . ◭
Let us give a simple characterization of the generalized Cayley graphs for the left-quasigroups. For the previous left-quasigroup M , its graph C(M ) is the following: We begin by characterizing these graphs. By Facts 2 and 3, G is deterministic, source-complete and simple. For any p, q ∈ M , we have p We now extend Proposition 29 to the generalized Cayley graphs of left-quasigroups. To do this, we must recall and define basic graph notions.

[ [p\q]] -→ G q hence G is complete. If in
Let G be a graph. For any vertex s, its out-degree In particular by Fact 2 and for any generalized Cayley graph G, G is of bounded out-degree ⇐⇒ G is finitely labeled. By removing the labeling of a graph G, we get the binary edge relation on V G :

δ + G (s) = |G ∩ {s}×A×V G | is the number of edges of source s. The out-degree of G is the cardinal ∆ + G = sup{ δ + G (s) | s ∈ V G }. We say that G is of bounded out-degree when ∆ + G is finite. We have ∆ + G = |A G | for G deterministic
-→ G = { (s, t) | ∃ a ∈ A G (s, a, t) ∈ G }. Let R ⊆ V ×V be a binary relation on a set V i.e. is an unlabeled graph. The image of P ⊆ V by R is the set R(P ) = { t | ∃ s ∈ P (s, t) ∈ R }. So the out-degree of s ∈ V is δ + R (s) = |R(s)| and ∆ + R = sup{ δ + R (s) | s ∈ V } is the out-degree of R.
For any graph G and any vertex s, we have δ + →G (s) ≤ δ + G (s) hence ∆ + →G ≤ ∆ + G , and we have equalities for G simple. A relation R is an out-regular relation if all the elements of V have the same out-degree:

|R(s)| = |R(t)| for any s, t ∈ V .
Let us give simple conditions on R so that its complement V ×V -R is out-regular.

◮ Lemma 31. Let R ⊆ V ×V and S = V ×V -R the complement of R w.r.t. V ×V .
If R is finite and out-regular then S is out-regular. If R is infinite and

∆ + R < |V | then S is out-regular. Proof. i) When R

D. Caucal XX:19

Hence S is out-regular on V with ∆ + S = |V |. ◭

We say that a graph G is out-regular if -→ G is out-regular i.e. all the vertices have the same number of targets. For instance

G = {s a -→ t , t a -→ s , t b -→ s} is out-regular since -→ G (s) = {t} and -→ G (t) = {s} while δ + G (s) = 1 and δ + G (t) = 2. We also say that G is co-out-regular if its unlabeled complement is out-regular i.e. (V G ×V G --→ G ) = / -→ G is
G --→ G (s)| = |V G --→ G (t)| for any s, t ∈ V G .
Let r be a vertex of G. Assume the axiom of choice. Let us apply the construction given in the proof of Theorem 25. As G is co-out-regular, we can now take for each vertex s a bijection f s from V G --→ G (r) to V G --→ G (s) and whose f r is the identity. As for the proof of Theorem 27, if G is loop-complete and r / -→ G r, we add the condition that f s (r) = s for any s ∈ V G . Thus <G> remains simple, deterministic, source-complete (resp. loop-complete) and is in addition a complete graph. By Proposition 28, (V G , × r ) is a left-quasigroup. By Proposition 23, r is a left-identity (resp. is an identity) and By adding edges, we transform G into the following complete graph:

G = C[ [V G , -→ G (r)] ] with [ [s] ] = a for any r a -→ G s. ◭ For instance, let G = { m 0 -→ 0 | m ≥ 0 } ∪ { m 1 -→ m + 1 | m ≥ 0 }
<G> = G ∪ { m n -→ n -1 | 2 ≤ n ≤ m + 1 } ∪ { m n -→ n | m ≥ 0 ∧ n > m + 1
} which remains simple, deterministic and source-complete. By Propositions 23 and 29, G = C(N, {0, 1}) for the left-quasigroup (N, × 0 ) of leftidentity 0 with the edge-operation × 0 of <G> defined for any m ≥ 0 by

m × 0 0 = 0 ; m × 0 n = n -1 ∀ 2 ≤ n ≤ m + 1 m × 0 1 = m + 1 ; m × 0 n = n ∀ n > m + 1.
Another example is given by a graph G of the following representation: It is simple, deterministic, co-out-regular, source-complete and loop-complete. By Theorem 32, this graph is a generalized Cayley graph of a left-quasigroup with an identity. Indeed, by replacing a by 0 and b by 1, G is isomorphic to the following graph:

H = { m 0 -→ m | m ≥ 0 } ∪ { 1 1 -→ 0 } ∪ { m 1 -→ 1 | m ≥ 0 ∧ m = 1 }.
We complete H into the graph:

<H> = { m 0 -→ m | m ≥ 0 } ∪ { m m -→ 0 | m ≥ 0 } ∪ { m n -→ n | m ≥ 0 ∧ n > 0 ∧ m = n }.
So <H> remains simple, deterministic, source-complete and loop-complete. Furthermore <H> is complete i.e. any vertex is an 1-root. By Proposition 23, the magma (N, × 0 ) with the edge-operation × 0 of <H> i.e.

m × 0 0 = m ; m × 0 m = 0 ; m × 0 n = n for any m, n ≥ 0 with m = n and n > 0 is a left-quasigroup of identity element 0. Furthermore G is isomorphic to C[ [N, {0, 1}] ] with [ [0] ] = a and [ [1] ] = b.
The co-out-regularity in Theorem 32 can not be removed. For instance, consider the monoid (N, +) which is is not a left-quasigroup. Its graph

C(N) = { m n -→ m + n | m, n ≥ 0 } is simple,
deterministic and source-complete. Furthermore we have 0 n -→ C(N) n for any n ≥ 0 while there is no edge from 1 to 0. By Proposition 29, this graph is not a generalized Cayley graph of a left-quasigroup. By Lemma 31, the co-out-regularity in Theorem 32 can be removed for the graphs of bounded out-degree which coincides with the characterization of Theorem 25. In this case, we can also remove the assumption of the axiom of choice.

◮ Theorem 33. For any finitely labeled graph G, the following properties are equivalent : a) G is a generalized Cayley graph of a left-cancellative magma (resp. with a right identity), b) G is a gen. Cayley graph of a left-quasigroups with a left identity (resp. an identity), c) G is simple, deterministic, source-complete (resp. and loop-complete). Let r be a vertex of G. For each vertex s, we associate the injective function:

ℓ s = { (a, b) | ∃ t (r a -→ G t ∧ s b -→ G t) }.
We define the following graph:

≪G≫ = { s p -→ t | ∃ a (r a -→G p ∧ s a -→G t) } ∪ { s p -→ t | ∃ a ∈ AG -Dom(ℓs) (r a -→G t ∧ s ℓs(a) -→ G p) } ∪ { s t -→ t | t ∈ VG -(-→G(r) ∪ -→G(s)) }.
For G of vertex set V G = {p, q, r, s, t, x} with the following edges from r and s :

V ≪G≫ = V G = A ≪G≫ . Furthermore ≪G≫ is complete with r s -→ ≪G≫ s for any s ∈ V G . By Proposition 23, we have ≪G≫ = C(V G ) for the left-cancellative magma (V G , × r ) of left identity r with s t -→ ≪G≫ s × r t for any s, t ∈ V G . Finally G = C[ [V G , -→ G (r)] ] with [ [s] ] = a for any r a -→ G s.
Now suppose that G is loop-complete. We distinguish the two complementary cases below. Case 1 : all the vertices of G have a loop of the same label.

Then ≪G≫ remains loop-complete and by Proposition 23, r is an identity of × r . Case 2 : G has no loop.

We take a new label a ∈ A -A G and we redefine ≪G≫ as being

≪G ′ ≫ for G ′ = G ∪ { s a -→ s | s ∈ V G }.
We conclude by Case 1. ◭

For the previous example, we have ≪H≫ = <H>.

For the penultimate example, we have

≪G≫ = { m 1 -→ m + 1 | m ≥ 0 } ∪ { m m+1 -→ 1 | m ≥ 0 } ∪ { m n -→ n | m, n ≥ 0 ∧ n = 1 ∧ n = m + 1 }.
For the last example of the previous section (after Theorem 27), we have

≪G≫ = { 0 m ε -→ 0 m | m ≥ 0 } ∪ { 0 m 0 -→ 0 m+1 | m ≥ 0 } ∪ { 0 m 0 m -→ ε | m > 0 } ∪ { 0 m 0 m+1 -→ 0 | m > 1 } ∪ { 0 00 -→ ε } ∪ { 0 m u -→ u | u ∈ 0 * N + * -{ε, 0, 0 m , 0 m+1 } } ∪ { ui ε -→ ui | u ∈ 0 * N + * ∧ i ∈ N + } ∪ { ui 0 -→ u | u ∈ 0 * N + * ∧ i ∈ N + } ∪ { ui ui -→ ε | u ∈ 0 * N + * -{ε} ∧ i ∈ N + } ∪ { ui u -→ 0 | u ∈ 0 * N + * ∧ i ∈ N + } ∪ { i i -→ 0 | i ∈ N + } ∪ { ui v -→ v | u, v ∈ 0 * N + * ∧ i ∈ N + ∧ v ∈ {ε, 0, u, ui} }.

Generalized Cayley graphs of quasigroups

We can now refine the previous characterization of generalized Cayley graphs from leftquasigroups (Theorem 32) to quasigroups (Theorem 41).

A magma (M, •) is a quasigroup if • obeys the Latin square property: for each p, q ∈ M, there is a unique r ∈ M such that p•r = q denoted by r = p\q the left quotient of q by p, there is a unique s ∈ M such that s•p = q denoted by s = q/p the right quotient of q by p.

XX:22 Cayley graphs

This property ensures that each element of M occurs exactly once in each row and exactly once in each column of the Cayley table for • . The previous finite left-quasigroup is not a quasigroup. On the other hand, ({a, b, c}, •) is a quasigroup with • defined by the Cayley table:

Note that • is not associative: a • (b • c) = a and (a • b) • c = c. Furthermore, M is a quasigroup ⇐⇒ M is cancellative and p • M = M = M • p for any p ∈ M .
Let us refine Proposition 28 in the case where the graph is also co-deterministic and targetcomplete.

◮ Proposition 34. Let G be a graph which is simple, deterministic and co-deterministic, complete, source-complete and target-complete. For any vertex r, (V G , × r ) is a quasigroup.

Proof.

Let r be a vertex of G and • be the edge-operation × r . By Proposition 28,

(V G , •) is a left-quasigroup. i) Let us check that (V G , •) is right-cancellative. Assume that s • t = s ′ • t.
As G is complete, there exists a such that r

a -→ G t. By definition of • we have s a -→ G s • t and s ′ a -→ G s ′ • t = s • t. As G is co-deterministic, we get s = s ′ . ii) Let t ∈ V G . Let us check that V G ⊆ V G • t . Let s ∈ V G . As G is complete, there exists a ∈ A G such that r a -→ G t. As G is target-complete, there exists s ′ ∈ V G such that s ′ a -→ G s. By definition of • we have s ′ a -→ G s ′ • t. As G is deterministic, we get s = s ′ • t. ◭

D. Caucal

XX:23

By Fact 3, G is co-deterministic. For any p, q ∈ M , we have p/q x for any x > 0. We now adapt Theorem 32 to the quasigroups. This will require a much more extensive development than what has been done with Theorem 32. For any vertex s of a graph G, its in-degree δ -

[ [q]] -→ G p hence G is target-complete. If in
G (s) = |G ∩ V G ×A×{s}| = δ + G -1 (s) is the number of edges of target s, and δ G (s) = δ + G (s) + δ - G (s) is the degree of s. The in-out-degree of G is the cardinal ∆ G = sup { δ + G (s) | s ∈ V G } ∪ { δ - G (s) | s ∈ V G } . We say that a graph G is of bounded degree when ∆ G is finite. Let R ⊆ V ×V be a binary relation on a set V . The in-degree of s ∈ V is δ - R (s) = |R -1 (s)| for R -1 = { (t, s) | (s, t) ∈ R } the inverse of R. The in-out-degree of R is ∆ R = sup { δ + R (s) | s ∈ V } ∪ { δ - R (s) | s ∈ V } . A relation R is a regular relation on V if |R(s)| = |R -1 (s)| = ∆ R for any s ∈ V . Let us apply Lemma 31 to R and R -1 . ◮ Corollary 36. Let R ⊆ V ×V and S = V ×V -R the complement of R w.r.t. V ×V .
If R is finite and regular then S is regular. If R is infinite and ∆ R < |V | then S is regular.

An edge-labeling of R is a mapping c : R -→ A defining the respective graph and color set

R c = { (s, c(s, t), t) | (s, t) ∈ R } and c(R) = { c(s, t) | (s, t) ∈ R } = A R c .
An edge-coloring of R is an edge-labeling c of R such that R c is a deterministic and co-deterministic graph. In that case, we say that R is |c(R)|-edge-colorable and we have |c(R)| ≥ ∆ R . We will give general conditions for a relation R to be ∆ R -edge-colorable. An undirected edge-coloring of R is an edge-labeling c of R such that two adjacent couples of R have distinct colors: for any (s, t) , (s

′ , t ′ ) ∈ R, if (s, t) = (s ′ , t ′ ) and {s, t} ∩ {s ′ , t ′ } = ∅ then c(s, t) = c(s ′ , t ′ ).
Any undirected edge-coloring is an edge-coloring.

Let V ′ = { s ′ | s ∈ V } be a disjoint copy of V i.e. ′ is a bijection from V to a disjoint set V ′ . We transform any relation R ⊆ V ×V into the relation R ′ = { (s, t ′ ) | (s, t) ∈ R } ⊆ V ×V ′
and any edge-labeling c of R into the edge-labeling c ′ of R ′ defined by c ′ (s, t ′ ) = c(s, t) for any (s, t) ∈ R.

So ∆ R = ∆ R ′ and for any edge-labeling c of R,

c is an edge-coloring of R ⇐⇒ c ′ is an edge-coloring of R ′ ⇐⇒ c ′ is an undirected edge-coloring of R ′ .
As R ′ ⊆ V ×V ′ with V ∩ V ′ = ∅, R ′ is a bipartite relation hence for R ′ finite, and by König's theorem [START_REF] König | Gráfok és mátrixok[END_REF], R ′ has an undirected edge-∆ R ′ -coloring . This implies that we have an edge-coloring of any finite relation R using ∆ R colors.

◮ Lemma 37. Any finite binary relation R is ∆ R -edge-colorable.

Proof.

Instead of applying König's theorem to R ′ , we will adapt its standard proof directly to R.

Let n ≥ 0, R = {(s 1 , t 1 ), . . . , (s n , t n )} and k = ∆ R . By induction on 0 ≤ i ≤ n, let us construct an edge-coloring c i of R i = {(s 1 , t 1 ), . . . , (s i , t i )} in [k] = {1, . . . , k}.

For i = 0, the empty function c 0 is an edge-coloring of R 0 = ∅. Let 0 ≤ i < n and c i be an edge-coloring of R i in [k]. We denote by s = s i+1 , t = t i+1 ,

O s = { c i (s, q) | (s, q) ∈ Dom(c i ) } and I t = { c i (p, t) | (p, t) ∈ Dom(c i ) }.
We distinguish the two complementary cases below. Case 1 : O s ∪ I t ⊂ {1, . . . , k}. We extend c i to the edge-coloring c i+1 of R i+1 by defining As R ci is deterministic and co-deterministic, there are unique s ′ and t ′ such that c i (s, t ′ ) = a and c i (s ′ , t) = b. This is illustrated as follows:

c i+1 (s, t) = min{ j | j ∈ O s ∪ I t }.
t ′ a ←-s -→ t b
←-s ′ where the labeled relation x -→ for any x ∈ {1, . . . , k} is defined by

x -→ = { (p, q) ∈ Dom(c i ) | c i (p, q) = x }.
Let us consider the chain in R ci of maximal length and of the form -→ t is not an edge of this chain. We define another edge-labeling c of R i by exchanging the labels a and b for the edges of the chain: for any (p, q) ∈ Dom(c i ),

c(p, q) =      b if p a -→ q is an edge of the chain a if p b
-→ q is an edge of the chain ci(p, q) otherwise.

Thus R c

i remains deterministic and co-deterministic i.e. c is an edge-coloring of R i with c(s, t ′ ) = c(s ′ , t) = b. It remains to add c(s, t) = a to get an edge-coloring of R i+1 in [k]. ◭ Under the assumption of the axiom of choice (actually under the weaker assumption of the ultrafilter axiom), let us generalize Lemma 37. For this we use a coloring on the vertices instead on the edges. A vertex-coloring of R ⊆ V ×V is a mapping c : V -→ A such that c(s) = c(t) for any (s, t) ∈ R, and in that case, we say that R is |c(V )|-vertex-colorable. Note that a relation with a reflexive pair has no vertex-coloring. The dual of R is the binary relation D(R) on R defined by

D(R) = { ((r, s) , (r, t)) | (r, s) , (r, t) ∈ R ∧ s = t } ∪ { ((s, r) , (t, r)) | (s, r) , (t, r) ∈ R ∧ s = t }.
For any edge-labeling c of R, c is an edge-coloring of R ⇐⇒ c is a vertex-coloring of D(R).

Thus by Lemma 37 and for any finite relation R, D(R) has a ∆ R -vertex-coloring. We can apply the compactness theorem [START_REF] De Bruijn | A color problem for infinite graphs and a problem in the theory of infinite relations[END_REF] to extend Lemma 37 to any relation of bounded degree.

S = { (s, t) | s, t ∈ V G ∧ {s}×A G ×{t} ∩ G ′ = ∅ } is a regular relation on V G .
By Proposition 40, S has a complete ∆ S -edge-coloring c i.e. S c is a deterministic, codeterministic, source and target-complete graph. By definition, S c is also simple.

Furthermore we can assume that A

G ∩ A S c = ∅. Let H = G ′ ∪ S c
. Thus H is source and target-complete. It is also complete, simple, deterministic and co-deterministic. Furthermore for G loop-complete, H is loop-complete. Let r be a vertex of G. By Proposition 34, (V G , × r ) is a quasigroup for the edgeoperation × r of H. By Proposition 23, r is a left-identity (resp. is an identity) and

H = C[ [V G , -→ H (r)] ] with [ [s] ] = a for any r a -→ H s. By label restriction to A G , G = C[ [V G , -→ G (r) ] ] is a generalized Cayley graph of (V G , × r ).
◭

The co-regularity in Theorem 41 can not be removed. For instance, the following graph:

PlusMinus = { i + 2mj j -→ i + (2m + 1)j | m ≥ 0 ∧ 0 ≤ i < j } ∪ { i 0 -→ i | i ≥ 0 } ∪ { i + (2m + 1)j j -→ i + 2mj | m ≥ 0 ∧ 0 ≤ i < j }
is deterministic, co-deterministic, simple, source-complete and target-complete. Furthermore it is not complete: there is no edge between 1 and 2 and more generally between i + (2m + 1)j and i + (2m + 2)j for any m ≥ 0 and 0 ≤ i < j. Finally it is 0-complete: 0 j -→ j for any j ≥ 0. By Proposition 35, PlusMinus is not a generalized Cayley graph of a quasigroup. By Corollary 36, the co-regularity in Theorem 41 can be removed for the graphs of bounded degree which corresponds by Fact 30 to the finitely labeled graphs G when G and G -1 are deterministic and source-complete.

◮ Corollary 42. In ZFC set theory, a finitely labeled graph is a generalized Cayley graph of a quasigroup iff it is deterministic, co-deterministic, simple, source and target-complete.

For instance the following graph of all the cycles:

Cycles = { (m, n) a -→ (m, n + 1 (mod m)) | m > n ≥ 0 } is

XX:28 Cayley graphs

For all the generalized Cayley graphs (not necessarily finitely labeled), we need the co-outregularity for the left-quasigroups, and the co-regularity for the quasigroups.

Decidability results

We have given graph-theoretic characterizations of generalized Cayley graphs of various basic algebraic structures. These characterizations are adapted to decide whether a graph G is a generalized Cayley graph, and if so, we got

G = C[ [V G , -→ G (r)]
] with [ [s] ] = a for any r a -→ G s for the operation on V G which is either the path-operation * r with r a root, or the chainoperation * r , or the extended chain-operation * P with P a representative set of Comp(G), or the edge-operation <G> × r for some completion <G> of G and for any vertex r. We will show the effectiveness of these characterizations and their associated operations for a general family of infinite graphs. We restrict to the family of end-regular graphs of finite degree [START_REF] Muller | The theory of ends, pushdown automata, and second-order logic[END_REF] which admits an external characterization by finite decomposition by distance which allows to decide the isomorphism problem, and an internal characterization as suffix graphs of word rewriting systems which have a decidable monadic second-order logic.

End-regular graphs

A marked graph is a couple (G, P ) of a graph G with a vertex subset P ⊆ V G . We extend the graph isomorphism to the marked graphs: (G, P ) ≡ (G ′ , P ′ ) if G ≡ g G ′ for some isomorphism g such that g(P ) = P ′ , and we also write (G, P ) ≡ g (G ′ , P ′ ). Let G be a graph. The frontier Fr G (H) of H ⊆ G is the set of vertices common to H and G -H :

Fr G (H) = V H ∩ V G-H
and we denote by End G (H) the set of ends obtained by removing H in G :

End G (H) = { (C, Fr G (C)) | C ∈ Comp(G -H) }.
We say that G is end-regular if there exists an increasing sequence H 0 ⊆ . . . ⊆ H n ⊆ . . . of finite subgraphs H n of G such that G = n≥0 H n and n≥0 End G (H n ) is of finite index for ≡ . Note that any end-regular graph is finitely labeled and of finite or countable vertex set. Furthermore any end-regular graph of finite degree is of bounded degree. Moreover, every end-regular graph has only a finite number of non-isomorphic connected components. We say that the previous sequence (H n ) n≥0 is a compatible decomposition of G if it also satisfies that two isomorphic ends have the same decomposition in the following sense: for any m, n ≥ 0 and any (C,

P ) ∈ End G (H m ) and (D, Q) ∈ End G (H n ), if (C, P ) ≡ g (D, Q) then C ∩ H m+p ≡ g D ∩ H n+p
for every p ≥ 0. Any end-regular graph has a compatible decomposition which can be finitely presented by a deterministic graph grammar [START_REF]Caucal Deterministic graph grammars[END_REF]. Any finite graph is end-regular. Any regular tree (having a finite number of non isomorphic subtrees) is end-regular. Except for the quater-grid and the graph Cycles, all other graphs in this article are end-regular. The following infinite graph: This graph is formed by two disjoint source-complete {a, b}-trees whose every node of a tree is connected by a c-edge to the corresponding node of the other tree. The graph Ξ is end-regular since it is generated by the graph grammar [START_REF]Caucal Deterministic graph grammars[END_REF] reduced to this unique rule: Note that Ξ is strongly connected and of bounded degree, simple, deterministic and codeterministic, source-complete but not target-complete, arc-symmetric but not symmetric. By Theorem 8, Ξ is a Cayley graph of a cancellative monoid.

Ξ = { ui x -→ uxi | u ∈ {a, b} * ∧ x ∈ {a, b} ∧ i ∈ {0, 1} } ∪ { ui c -→ u(1 -i) | u ∈ {a, b} * ∧ i ∈ {0, 1} }
Precisely Ξ = C[ [V Ξ , {a0, b0, 1}] ] with [ [a0] ] = a, [ [b0] ] = b, [ [1]
] = c for the cancellative monoid (V Ξ , * 0 ) with the path-operation * 0 defined for any u, v ∈ {a, b} * and i, j ∈ {0, 1} by ui * 0 vj = uvk with k = i + j (mod 2).

By Theorem 33, Ξ is also a generalized Cayley graph of a left-quasigroup with an identity, namely ({a, b} * .{0, 1}, •) for • the edge-operation × 0 of a completion ≪Ξ≫ that we can define for any u ∈ {a, b} * , x ∈ {a, b}, i ∈ {0, 1} by

ui • x0 = uxi ; ui • uxi = x0 for ui = x0 ; x0 • xx0 = 0 ui • 0 = ui ; ui • 1 = u(1 -i) ; ui • u(1 -i) = 1 ui • v = v otherwise.
The end-regularity of a graph can also be expressed on the vertices.

A graph G is vertex- end-regular if V G = n≥0 V n with V 0 ⊆ . . . ⊆ V n ⊆ . . . finite and n≥0 End G (G |Vn ) is of finite index for ≡ .
This notion of vertex-end-regularity corresponds to the (edge-)end-regularity.

◮ Lemma 43. A graph is end-regular if and only if it is vertex-end-regular.

Proof.

⇐= : G n = G |Vn suits. =⇒ : V n = V Gn suits since G -G |Vn = G -G n ∪ K∈Comp(G-Gn) G |FrG(K) . ◭
We say that a graph G is by distance from a vertex r if it is vertex-end-regular for the sequence defined by V n = { s | d G (r, s) ≤ n } for any n ≥ 0. In that case, G is connected and of finite degree. Furthermore the sequence (H n ) n≥0 defined by This normalization of the regularity by distance implies that for any end-regular graph G of finite degree, the isomorphism problem is decidable: from any finite compatible decomposition of G, we can decide whether s ≃ G t by comparing by distance G from s with G from t [START_REF]On the regular structure of prefix rewriting[END_REF].

H n = G |Vn = { (s, a, t) ∈ G | d G (r, s) ≤ n ∧ d G (
◮ Corollary 45. For any end-regular graph G of finite degree, ≃ G is decidable.

The representation of an end-regular graph G by a graph grammar is an external representation of G, namely which is up to isomorphism: the vertices of G are not taken into account.

To obtain decidable logical properties on G, we need to give an internal representation of G, namely by an isomorphic graph whose vertices are words.

Suffix recognizable graphs

Another way to describe the end-regular graphs of finite degree is through rewriting systems.

A labeled word rewriting system R over an alphabet N is a finite A-graph of vertex set As the existence of a chain between two vertices can be expressed by a monadic (second order) formula, any connected component of N * .R can be obtained by a monadic interpretation in T N . As T N has a decidable monadic theory [START_REF] Rabin | A simple method for undecidability proofs and some applications[END_REF] and by Proposition 46, any connected end-regular graph has a decidable monadic theory. This is generalized [START_REF] Angluin | Regular prefix relations[END_REF][START_REF] Läuchli | Monadic second order definable relations on the binary tree[END_REF] to the suffix recognizable graphs over N which are the graphs of the form n i=1 W i (U i ai -→ V i ) where n ≥ 0 and U 1 , V 1 , W 1 , . . . , U n , V n , W n ∈ Rec(N * ) for Rec(N * ) the family of recognizable (regular) languages over N .

In this corollary, we do not need the connected condition for the symmetry since any endregular graph has only a finite number of non-isomorphic connected components. We can establish the effectiveness of previous Cayley graph characterizations for the regular graphs of finite degree. This decidability result does not require the assumption of the axiom of choice.

◮ Theorem 54. We can decide whether a suffix recognizable graph G of finite degree is a Cayley graph of a left-cancellative monoid, of a cancellative monoid, of a group, and whether G is a generalized Cayley graph of a left-quasigroup, of a quasigroup, of a group. It remains to check that the path-operation * r is computable. We just need that G is deterministic and arc-symmetric. Let s, t ∈ V G . By Proposition 6, s * r t is a vertex that we can determine. The label set L G (r, t) = { u ∈ A * G | r u -→ G t } of the paths from r to t is an effective non empty context-free language [START_REF]On the regular structure of prefix rewriting[END_REF] : we can construct a pushdown automaton recognizing L G (r, t) hence we can compute a word u ∈ L G (r, t). Thus s * r t is the target of the path from s labeled by u i.e. s u -→ G s * r t.

ii) By Proposition 47 and Corollary 53, we can decide whether G is connected, symmetric, deterministic and co-deterministic i.e. by Theorem 17, whether G is a Cayley graph of a group. In the affirmative and by Proposition 16, it remains to check that the chain-operation * r is computable where r is any vertex of G. We have seen that G * r = G * r . As r is a root of G which is deterministic and arc-symmetric and by (i), * r is computable.

iii) As G has a decidable first order theory, we can decide whether G is simple, deterministic, source-complete i.e. by Theorem 33, whether G is a generalized Cayley graph of a left-quasigroup. In the affirmative and by Propositions 23 and 28, it remains to check that the edge-operation ≪G≫ × r is computable where r is any vertex and ≪G≫ is the completion of G defined in the proof of Theorem 33. This edge-operation that we denote by • has been defined for any s, t ∈ V G by

iv)

As G has a decidable first order theory, we can decide whether G is simple, deterministic, co-deterministic, source and target-complete i.e. by Corollary 42 and under the assumption of the axiom of choice, whether G is a generalized Cayley graph of a quasigroup. Assume that G is simple, deterministic, co-deterministic, source and target-complete. In fact, we do not need the assumption of the axiom of choice: we will define a computable quasigroup operation on V G .

p

  It is simple, deterministic, co-deterministic, complete, source-complete and target-complete. The vertex-restriction G |P of G to a set P is the induced subgraph of G by P ∩ V G :

For instance let us

  consider a graph G of the following representation:

  and we have G = C[ [V G , {<a>, <b>}] ] with [ [<a>] ] = a and [ [<b>] ] = b. Propositions 4 and 6 give a graph-theoretic characterization of the Cayley graphs of leftcancellative monoids.

i)

  Suppose there are m, e ∈ M such that m•e = m. In this case, let us check that e is an identity element. We have m•(e•e) = (m•e)•e = m•e. As • is left-cancellative, we get e•e = e. Let n ∈ M . So (n•e)•e = n•(e•e) = n•e. As • is right-cancellative, we get n•e = n. Finally e•(e•n) = (e•e)•n = e•n. As • is left-cancellative, we get e•n = n.

  r is the root of G ; we say that G is rootable into G. For instance the following non connected graph:

  and [ [-1] ] = b for the following associative and cancellative path-operation * defined by m * n = sign(m×n) (|m| + |n|) for any m, n ∈ Z -{0}.

  Cayley graph of a group: it is isomorphic to C[ [Z, {2, -1}] ] for the group (Z, +) with [ [2] ] = a and [ [-1] ] = b.

For

  instance by Proposition 16, a graph of the following representation: graph of a group: it is isomorphic to C[ [Z×{0, 1}, {(1, 0), (0, 1)}] ] with [ [(1, 0)] ] = a, [ [(0, 1)] ] = b and for the chain-operation (m, i) * (0,0) (n, j) = (m + n, i + j (mod2)). It is also isomorphic to the Cayley graph of the group of finite presentation < a, b | ab = ba, b 2 = 1 >.

◮

  r. Thus r is a right identity. ◭ We get a fully graph-theoretic characterization of the Cayley graphs C[ [M ] ] for any leftcancellative magma M with a left identity. Proposition 24. A graph is equal to C[ [M ] ] for some left-cancellative magma M with a left identity if and only if it is simple, deterministic, source-complete and 1-rooted. Proof. =⇒ : let G = C[ [M ] ] for some left-cancellative magma (M, •) with a left identity r, and some injective mapping [ [ ] ]. By Facts 2 and 3, G is deterministic, source-complete and simple. By Fact 21, r is an 1-root of G. ⇐= : By Proposition 23. ◭ Under the assumption of the axiom of choice, we can characterize the generalized Cayley graphs of left-cancellative magmas. ◮ Theorem 25. In ZFC set theory, the following graphs define the same family : a) the generalized Cayley graphs of left-cancellative magmas, b) the generalized Cayley graphs of left-cancellative magmas with a left identity, c) the simple, deterministic, source-complete graphs. Proof. b) =⇒ a) : immediate. a) =⇒ c) : by Facts 2 and 3. c) =⇒ b) : let G be a simple, deterministic and source-complete graph. Assume the axiom of choice. Let r be a vertex of G with

  Proposition 24 and Fact 22. ⇐= : By Proposition 23. ◭ We restrict Theorem 25 to left-cancellative magmas having a right identity. ◮ Theorem 27. In ZFC set theory, the following graphs define the same family : a) the generalized Cayley graphs of left-cancellative magmas with a right identity, b) the generalized Cayley graphs of left-cancellative magmas with an identity, c) the simple, deterministic, source-complete and loop-complete graphs. Proof. b) =⇒ a) : immediate. a) =⇒ c) : By Facts 2, 3, 22. c) =⇒ b) : Let G be a graph which is simple, deterministic, source and loop-complete.

  Note that • is not associative since c • (b • c) = a and (c • b) • c = c, and is not rightcancellative since a•b = c•b. The first figure in Section 3 is a representation of C(M ) for the semigroup M = {a, b} with x•y = y for any x, y ∈ M . This semigroup is also a left-quasigroup which is not right-cancellative. Any left-quasigroup M is left-cancellative. The converse is true for M finite but is false in general: (N, +) is cancellative but is not a left-quasigroup. Indeed, M is a left-quasigroup ⇐⇒ M is left-cancellative and p•M = M for any p ∈ M .

XX:18 Cayley graphs ◮

 graphs Proposition 29. We have the following equivalences : a) a graph is equal to C[ [M ] ] for some left-quasigroup M (resp. with a right identity), b) a graph is equal to C[ [M ] ] for some left-quasigroup M with a left identity (resp. identity), c) a graph is simple, deterministic, complete, source-complete (resp. and loop-complete). Proof. b) =⇒ a) : immediate. a) =⇒ c) : let G = C[ [M ] ] for some left-quasigroup (M, •) and injective mapping [ [ ] ].

  addition M has a right identity then, by Fact 22, G is loop-complete. c) =⇒ b) : by Propositions 23 and 28. ◭ For instance the magma M = {0, 1} with i • j = 1j for any i, j ∈ {0, 1}, is a leftquasigroup without left and right identity element. By Propositions 23 and 28, the magma N = {0, 1} with the edge-operation × 0 of C(M ) defined by i × 0 j = j for any i, j ∈ {0, 1} is a left-quasigroup with 0 and 1 are left identities, and C(M ) = C[ [N ] ] where [ [0] ] = 1 and [ [1] ] = 0.

◮

  and source-complete. Fact 30. For any vertex s of a graph G, we have δ + G (s) ≤ |A G | for G deterministic, and |A G | ≤ δ + G (s) for G source-complete.

  is finite, we have S(s) = |V | -|R(s)| for any s ∈ V . In addition for R out-regular and for any s, t ∈ V , |R(s)| = |R(t)| hence |S(s)| = |S(t)|. ii) When R is infinite with ∆ + R < |V |, we have |S(s)| = |V | for any s ∈ V .

  an out-regular relation on V G . Under the assumption of the axiom of choice, we can characterize the generalized Cayley graphs of left-quasigroups. ◮ Theorem 32. In ZFC set theory, the following graphs define the same family : a) the generalized Cayley graphs of left-quasigroups (resp. with a right identity), b) the generalized Cayley graphs of left-quasigroups with a left identity (resp. an identity), c) the simple, deterministic, source-complete (resp. and loop-complete) co-out regular graphs. Proof. b) =⇒ a) : immediate. a) =⇒ c) : let G = C[ [M, Q] ] for some left-quasigroup M and Q ⊆ M . By Proposition 29, G = C[ [M ] ] | [ [Q]] remains simple, deterministic and source-complete. For any s ∈ M , δ + → / G (s) = |M -Q| hence G is co-out-regular. If in addition M has a right identity then, by Fact 22, G is loop-complete. c) =⇒ b) : let G be a graph which is simple, deterministic, co-out-regular, source-complete (resp. and loop-complete). The co-out-regularity of G means that |V

  be the graph that we had considered after Theorem 25 and represented by

  =⇒ a) : immediate. a) =⇒ c) : by Facts 2,3,22. c) =⇒ b) : let G be a simple, deterministic and source-complete graph of finite label set. By Fact 30, G is of bounded out-degree. To each injective function ℓ : A G -→ A G , we associate a permutation ℓ on A G extending ℓ i.e. ℓ(a) = ℓ(a) for every a ∈ Dom(ℓ).

r

  ≪G≫ has the following edges from s : Thus ≪G≫ remains simple, deterministic, source complete with

  Its Cayley graph C({a, b, c}) is represented as follows:

◮

  Let us restrict Proposition 29 to the quasigroups. Proposition 35. We have the following equivalences : a) a graph is equal to C[ [M ] ] for some quasigroup M (resp. with a right identity), b) a graph is equal to C[ [M ] ] for some quasigroup M with a left identity (resp. an identity), c) a graph is simple, deterministic, co-deterministic, complete, source-complete, (resp. and loop-complete). Proof. b) =⇒ a) : immediate. a) =⇒ c) : let G = C[ [M ] ] for some quasigroup (M, •) and injective mapping [ [ ] ]. By Proposition 29, G is simple, deterministic, complete and source-complete.

  addition M has a right identity then, by Fact 22, G is loop-complete. c) =⇒ b) : By Propositions 23 and 34. ◭ For instance let us consider the division ÷ on R + = ]0, +∞[. So (R + , ÷) is a quasigroup of right identity 1. Furthermore × 1 is the multiplication on R + . Thus C(R + ) for the quasigroup (R + , ÷) is equal to C[ [R + ] ] for the group (R + , × 1 ) with [ [x] ] = 1

Case 2 :

 2 O s ∪ I t = {1, . . . , k}. As (s, t) ∈ Dom(c i ), we have |O s | < k and |I t | < k. So ¬(O s ⊆ I t ) and ¬(I t ⊆ O s ). Thus there exists a ∈ O s -I t and b ∈ I t -O s . In particular a = b.

  As b ∈ O s and R ci is deterministic and co-deterministic, this chain is finite. As a ∈ I t , s ′ b

For

  any s ∈ M , δ + → / G (s) = δ - → / G (s) = |M -Q| hence G is co-regular.If in addition M has a right identity then, by Fact 22, G is loop-complete. c) =⇒ b) : let G be a graph which is simple, deterministic and co-deterministic, source and target-complete. So G is regular with∆ G = |A G |. If G is without loop (hence G is loop-complete) then we take a new label a ∈ A -A G and we define G ′ = G ∪ { s a -→ s | s ∈ V G }.If G has at least one loop, we put G ′ = G. Moreover, suppose also that G is co-regular. By definition, the complement relation of G ′

  by Corollary 42 a generalized Cayley graph of a quasigroup. Let us summarize the characterizations obtained in ZFC theory for the finitely labeled generalized Cayley graphs. Left-quasigroups Left-cancellative magmas Quasigroups + co-deterministic + target-complete (41) Groups simple + deterministic + source-complete (33) + symmetric (20)

  of vertex set {a, b} * .{0, 1} is represented below.

a

  V R ⊂ N * i.e. R ⊂ N * ×A×N * and R is finite. Each edge u a -→ R v is a rule labeled by a, of left hand side u and right hand side v. The suffix graph of is the graphN * .R = { wu a -→ wv | (u, a, v) ∈ R ∧ w ∈ N * }.For instance let us consider the rewriting system R over N = {a, b, 0, 1} defined by 0 The connected component of the suffix graph N * .R of vertex 0 is equal to the graph Ξ. These suffix graphs give an internal representation of the end-regular graphs of finite degree[START_REF]On the regular structure of prefix rewriting[END_REF].◮ Proposition 46. A connected graph of finite degree is end-regular if and only if it is isomorphic to a connected component of a suffix graph.Any suffix graph N * .R can be obtained by a first order interpretation in the source-complete N -treeT N = { u a -→ ua | u ∈ N * ∧ a ∈ N } i.e. N * .R = { u a -→ v | T N |= φ a (u, v) } where for any a ∈ A R , φ a is the following first order formula φ a (x, y) : (u,a,v)∈R ∃ z (z u -→ x ∧ z v -→ y)and the path relation x a1...an -→ y for n ≥ 0 and a 1 , . . . , a n ∈ A R can be expressed by the first order formula ∃ z 0 , . . . , z n (z 0 a1 -→ z 1 ∧ . . . ∧ z n-1 an -→ z n ∧ z 0 = x ∧ z n = y).

  In the affirmative, G = C[ [V G , -→ G (r)] ] where [ [s] ] = a for any r a -→ G s and with a computable suitable binary operation on V G and vertex r. Proof. i) By Proposition 47 and Corollary 53, we can decide whether G is rooted, simple, arcsymmetric, deterministic (resp. and co-deterministic) i.e. by Theorem 7 (resp. Theorem 8) whether G is a Cayley graph of a left-cancellative monoid (resp. cancellative monoid). In the affirmative and by Proposition 6, (V G , * r ) is a left-cancellative (resp. cancellative) monoid where r is a root of G, and G = C[ [V G , -→ G (r)] ] where [ [s] ] = a for any r a -→ G s.

-→ s • t for s b -

 b →G t and (a, b) ∈ ℓs -ℓs s • t = t for t ∈ VG -(-→G(r) ∪ -→G(s))whereℓ s = { (a, b) | ∃ t (r a -→ G t ∧ s b -→ G t) } and to each injective function ℓ : A G -→ A G , we have associated a permutation ℓ on A G extending ℓ. Thus • is computable.Moreover we can check that • is an effective ternary suffix-recognizable relation.

  Cayley graph of a cancellative monoid. Precisely and as for the previous graph, we associate to each word u ∈ b * a * the unique vertex <u> accessible from the root by the path labeled by u. By Proposition 6, (V G , * <ε> ) is a cancellative monoid where <b m a n > * <ε> <b p a q > = <b m+p a n+q > for any m, n, p, q ≥ 0.

	graph of a cancellative monoid. On the other hand and according to Proposition 6, a
	quater-grid G of the following representation:
	a	a
	b	b	b
	a	a
	b	b	b
	a	a
	is a and we have G = C[ [V G , {<a>, <b>}] ] with [ [<a>] ] = a and [ [<b>] ] = b.
	Recall that a Cayley graph of a semigroup M is a generalized Cayley graph C
	Theorem 8. A graph is a Cayley graph of a cancellative monoid if and only if
	it is rooted, simple, deterministic, co-deterministic, arc-symmetric.
	Proof.
	=⇒ : By Theorem 7 and Fact 3.
	⇐= : By Proposition 6.		◭
	The previous graph is not co-deterministic hence, by Theorem 8 or Fact 3, is not a Cayley

  the subsemigroup generated by Q. Theorem 8 can be easily extended into a characterization of the Cayley graphs of cancellative semigroups. Indeed, a semigroup without an identity is turned into a monoid by just adding an identity. Precisely a monoid-completion M of a semigroup M is defined by M = M if M has an identity element, otherwise M = M ∪ {1} whose 1 is an identity element of M : p•1 = 1•p = p for any p ∈ M . This natural completion does not preserve the left-cancellative property but it preserves the cancellative property.

	◮ Lemma 9. Any monoid-completion of a cancellative semigroup is a cancellative monoid.

  connected. Theorems 14 and 17 give respectively a characterization of the monoid Cayley graphs of groups, and the group Cayley graphs. We can now deduce a characterization of the generalized Cayley graphs of groups. First, let us apply Corollary 15 and Theorem 17.

	⇐= : By Proposition 16.	◭

◮ Corollary 18. The connected (resp. strongly connected) components of generalized Cayley graphs of groups are the (resp. monoid) Cayley graphs of groups.

Let us extend Proposition 16 for non connected graphs. Let a magma (P, •) for P a representative set of Comp(G). We define the extended chain-relation Chain G (P ) as the ternary relation on V G defined by (s, t, x) ∈ Chain G

30 Cayley graphs is

  a compatible decomposition of G. The regularity by distance is a normal form for the connected end-regular graphs of finite degree[START_REF]On the regular structure of prefix rewriting[END_REF][START_REF]Caucal Deterministic graph grammars[END_REF].◮ Proposition 44. For any connected graph G of finite degree,G is end-regular ⇐⇒ G is end-regular by distance from some vertex ⇐⇒ G is end-regular by distance from any vertex.

r, t) ≤ n } XX:

D. Caucal

XX:25

◮ Proposition 38. In ZFC set theory, any bounded degree relation R has a ∆ R -edgecoloring.

Proof.

Let k be a positive integer and R be a binary relation on a set V with ∆ R = k. It is equivalent to show that D(R) is k-vertex-colorable, or that D(R) is vertex-colorable using at most k colors. By de Bruijn-Erdös theorem [START_REF] De Bruijn | A color problem for infinite graphs and a problem in the theory of infinite relations[END_REF], it is equivalent to check that any finite subset of D(R) is vertex-colorable with at most k colors. Let S ⊆ D(R) with S finite. Let

and R |P = R ∩ P ×P the induced relation of R by P . So S ⊆ D(R |P ) which is finite. By Lemma 37, R |P is edge-colorable using ∆ R |P ≤ ∆ R = k colors. Finally D(R |P ) hence S are vertex-colorable using at most k colors.

◭

We now want to color a regular relation in a complete way. First we present a general way to extend an injection into a bijection avoiding given sets.

◮ Lemma 39. Let X, Y be equipotent well orderable infinite sets. Let an injection p : P -→ Y for some subset P of X with |P | < |X|.

Let a sequence (P x ) x∈X-P of subsets of Y with |P x | < |Y | and such that |{ x ∈ X -P | y ∈ P x }| < |X| for every y ∈ Yp(P ). We can extend p into a bijection X -→ Y such that p(x) ∈ P x for every x ∈ X -P .

Proof.

Let < X be an initial well-ordering of X :

Let < Y be an initial well-ordering of Y . We define p on X -P by transfinite induction. Let x ∈ X -P . Let us define p(x) knowing p(x ′ ) for any x ′ < X x.

Thus p is injective and p(x) ∈ P x for every x ∈ X -P . Let us check that p is surjective. Assume that Im(p) = Y . Let

is source-complete and target-complete. Under the assumption of the axiom of choice, we can color in a complete way any regular relation.

◮ Proposition 40. In ZFC set theory, any regular relation R has a complete ∆ R -edgecoloring.

Proof.

Let R be a regular relation on a set V .

XX:26 Cayley graphs

We distinguish the two complementary cases below. Case 1 : ∆ R < ℵ 0 .

By Proposition 38, R has a ∆ R -edge-coloring c. So R c is a deterministic and co-deterministic graph with

Thus R c is source-complete and target-complete i.e. c is a complete edge-coloring.

Case 2 : ∆ R ≥ ℵ 0 . Under AC, it suffices to show the existence of a complete ∆ R -edge-coloring for R connected.

Under AC and having R connected, we have

Thanks to AC, let us consider an initial well-ordering < of V R . By transfinite induction, let us define a complete ∆ R -edge-coloring

First, we define c(λ, µ) for any (λ, µ) ∈ R with λ ≤ µ. This is illustrated below for ρ < λ ≤ µ.

For any µ ∈ R(λ) -P , we define

By Lemma 39, we can extend p into a bijection R(λ

Similarly, we define c(µ, λ) for any (µ, λ) ∈ R with λ < µ. This is illustrated below for ρ < λ < µ.

Under the assumption of the axiom of choice, we can restrict Theorem 32 to obtain a characterization of the generalized Cayley graphs of quasigroups.

◮ Theorem 41. In ZFC set theory, the following graphs define the same family : a) the generalized Cayley graphs of quasigroups (resp. with a right identity), b) the generalized Cayley graphs of quasigroups with a left identity (resp. an identity), c) the simple, deterministic, co-deterministic, co-regular, source-complete, target-complete (resp. and loop-complete) graphs.

remains simple, deterministic and co-deterministic, source and target-complete.

D. Caucal

XX:31

◮ Proposition 47. The suffix recognizable graphs over N are the graphs obtained by monadic interpretations in T N hence have a decidable monadic second order theory.

In particular, we can decide whether a suffix recognizable graph is rooted or is connected. We can also decide first order properties like the simplicity which can be expressed by the following first order formula:

-→ y and this the same for the properties of being deterministic, co-deterministic, source-complete, target-complete, and loop-complete. We still have to consider the decidability of the arc-symmetry and the symmetry of endregular graphs of finite degree. The suffix recognizable graphs form a strict extension of end-regular graphs that coincide for graphs of finite degree [START_REF]Caucal Deterministic graph grammars[END_REF].

◮ Proposition 48. Any end-regular graph is isomorphic to a suffix recognizable graph. Any suffix recognizable graph of finite degree is end-regular.

Note that a suffix recognizable graph over N of finite degree is of the form

By Proposition 48, these graphs constitute an internal representation of end-regular graphs of finite degree. Note also that

) is a suffix recognizable graph which is not an end-regular graph. By monadic interpretation (or by a simple saturation method on graph grammars), the family of end-regular graphs is closed under accessibility.

◮ Corollary 49. For any end-regular graph G and any vertex r, G ↓r is end-regular.

By Corollaries 45 and 49, we can decide whether s ↓ G t for G end-regular of finite degree.

◮ Corollary 50. For any end-regular graph G of finite degree, ↓ G is decidable.

The arc-symmetry of rooted graphs can be reduced to the accessible-isomorphism of a root with its successors. ◮ Lemma 51. A graph G of root r is arc-symmetric iff r ↓ G s for any r -→ G s.

Proof.

Let G be a graph with a root r such that r ↓ G s for any r -→ G s. Let us check that G is arc-symmetric i.e. r ↓ G s for any r -→ * G s. The proof is done by induction on n ≥ 0 for r -→ n G s. For n = 0, we have r = s. For n > 0, let t be a vertex such that r

Let us transpose Lemma 51 to the symmetric graphs. The arc-symmetry of connected graphs can be reduced to the isomorphism of a vertex with its adjacent vertices.

◮ Lemma 52. A connected graph with a vertex r is symmetric if and only if

Let us apply Lemma 51 and 52 with Corollaries 45 and 50.

◮ Corollary 53. We can decide whether a rooted (resp. any) end-regular graph of finite degree is arc-symmetric (resp. symmetric).

D. Caucal

XX:33

Let r be any vertex of G. By Proposition 34 (and as for the proof of Theorem 41), it is sufficient to define a complete graph H ⊇ G of vertex set V G with the same properties as G such that H × r is computable. When V G is finite and by Lemma 37, such a completion H is effective hence H × r is computable. We have to deal with the case where V G is infinite.

The set V G is a regular language over some finite alphabet that we order totally.

For any integer i ≥ 0, we can compute the i-th vertex v i by length-lexicographic order. We can assume that the finite label set A G is disjoint of N. Let us define a mapping T

-→ v j | i, j ≥ 0 }. By Lemma 39 and Proposition 40, T is defined for any i, j ≥ 0 by

Thus T is computable hence also H × r .

v)

As G has a decidable first order theory and by Corollary 53, we can decide whether G is simple, symmetric, deterministic and co-deterministic i.e. by Theorem 20 and under the assumption of the axiom of choice, whether G is a generalized Cayley graph of a group. Assume that G is simple, symmetric, deterministic and co-deterministic.

In fact, we do not need the hypothesis of the axiom of choice: we will define a computable extended chain-operation.

As G is a suffix-recognizable graph of finite degree over some alphabet N , it is of the form

regular language and we denote by

In G = {u 1 , . . . , u n } and Out G = {v 1 , . . . , v n }.

Let < ll be the length-lexicographic order extending a linear order on N .

Given languages L, M ⊆ N * , the left residual and the right residual of L by M are the respective languages:

Let C be a connected component of G. Thus V C is a regular language over N [START_REF] Büchi | Regular canonical systems[END_REF].

The left residual of C by a word w ∈ N * is the graph w

Thus w is prefix of any vertex of C and is denoted by C w. Let z C ∈ In G ∪ Out G be the minimal word by length lexicographic order such that C w.z C ∈ V C . Note that such a representative C w.z C of V C can be of non-minimal length and the words C w , z C are computable from any vertex of C. These words form the following representative set of Comp(G) :

This set is an effective regular language. Indeed, let D be a connected component of G with z C = z D . Thus ( C w) -1 C = ( D w) -1 D and we denote by

Let Rk(u) = |{ v ∈ P | v < ll u }| be the rank of u ∈ P according to < ll i.e. u is the Rk(u)-word in P by < ll . We have a group (P, +) for u + v defined for any u, v ∈ P by Rk(u + v) = Rk(u) + Rk(v) (mod |P |) for P finite, and for P countable, we consider the bijection : P -→ Z defined for any u ∈ P by

if Rk(u) is even,

-→ G x } of the chains between v x and x is an effective context-free language.

As G is symmetric, the extended chain-operation x • y has been defined by v x+y ℓxℓy -→ G x • y with ℓ x ∈ L x and ℓ y ∈ L y . Thus • is an effective group operation. ◭

We can consider the generalization of Theorem 54 to all the suffix-recognizable graphs (allowing vertices of infinite degree) which form the first level of a stack hierarchy for which any graph has a decidable monadic theory [START_REF] Carayol | The Caucal hierarchy of infinite graphs in terms of logic[END_REF]. To extend Theorem 54 to any graph of this hierarchy, we have to decide on the arc-symmetry (resp. symmetry) when these graphs are deterministic (resp. and co-deterministic).

The decidability result given by Theorem 54 is a first application of the

Conclusion

We obtained simple graph-theoretic characterizations for Cayley graphs of elementary algebraic structures. We have shown the effectiveness of these characterizations for infinite graphs having a structural regularity. This is only a first approach in the structural description and its effectiveness of Cayley graphs of algebraic structures.