domain: info math

text:
Bruno Courcelle
email: courcell@labri.fr

Unfoldings and Coverings of Weighted Graphs

Keywords: graph unfolding, graph covering, universal covering, regular tree, weighted graph, characteristic polynomial, graph factorization

Coverings of undirected graphs are used in distributed computing, and unfoldings of directed graphs in semantics of programs. We study these two notions from a graph theoretical point of view so as to highlight their similarities, as they are both dened in terms of surjective graph homomorphisms. In particular, universal coverings and complete unfoldings are innite trees that are regular if the initial graphs are nite. Regularity means that a tree has nitely many subtrees up to isomorphism. Two important theorems have been established by Leighton and Norris for coverings of nite graphs. We prove similar results for unfoldings of nite directed graphs. Moreover, we generalize coverings and similarly, unfoldings to graphs and digraphs equipped with nite or innite weights attached to edges of the covered or unfolded graphs. This generalization yields a canonical "factorization" of the universal covering of any nite graph, that (provably) does not exist without using weights. Introducing ω as an innite weight provides us with nite descriptions of regular trees having nodes of countably innite degree. Regular trees (trees having nitely many subtrees up to isomorphism) play an important role in the extension of Formal Language Theory to innite structures described in nitary ways. Our weighted graphs offer effective descriptions of the above mentioned regular trees and yield decidability results. We also generalize to weighted graphs and their coverings a classical factorization theorem of their characteristic polynomials.

Introduction

We rst review informally some basic notions and results. The notion of covering of an undirected graph has been introduced by Reidemeister [START_REF] Reidemeister | Einführung in die kombinatorische Topologie[END_REF] as a discrete analogue of coverings of surfaces. It has proved to be useful in the theory of distributed computing where a network is considered as an undirected graph N whose edges represent communication channels. The questions are whether certain problems such as the election problem (consisting in distinguishing a unique node of the network) can be solved by a distributed algorithm (of a certain type). This is possible if the graph N is minimal for the covering relation, equivalently if the universal coverings of N dened from any two different nodes are not isomorphic rooted trees. The universal covering of an undirected graph is an innite tree. It has a characterization in the sense of Category Theory and can be constructed as the innite tree of the walks in the graph originated from a node and that do not take the same edge twice in a row (in opposite directions). Starting from any two nodes yields isomorphic trees (without roots). Detailed denitions will be given in Section 4. The universal covering of a nite graph is a regular tree, i.e., a tree that has nitely many subtrees up to isomorphism (i.e., nitely many isomorphism classes of subtrees). The application of coverings to distributed computing was initiated by Angluin in [START_REF] Angluin | Local and global properties in networks of processors[END_REF].

Unfoldings of directed graphs are used in the study of abstract programs called transition systems in order to represent their semantics [START_REF] Arnold | Finite transition systems[END_REF][START_REF] Courcelle | The monadic second-order logic of graphs IX: Machines and their behaviours[END_REF][START_REF] Courcelle | Monadic second-order logic, graph coverings and unfoldings of transition systems[END_REF]. In particular, the complete unfolding1 of a directed graph equipped with a distinguished vertex (representing the "begin" instruction) is a rooted tree that is innite if the graph has directed cycles. The complete unfolding of the graph representing a transition system S encodes all computations of the program abstracted into S. If the graph is nite, its complete unfolding is a regular tree. Precise denitions will be given in Section 3.

We are interested in unfoldings and coverings from a graph theoretical point of view. Both notions are dened in terms of surjective graph homomorphisms that are bijective on the neighbourhoods of vertices related by the considered homomorphisms. The notion of neighbourhood is thus a parameter that gives rise to different but related notions: unfoldings, coverings and even others [START_REF] Courcelle | Monadic second-order logic, graph coverings and unfoldings of transition systems[END_REF]. For unfoldings of directed graphs, the neighbourhood of a vertex x is the set of edges outgoing from x. For coverings of undirected graphs, it is the set of edges incident to x. We study unfoldings and coverings by means of graph homomorphisms, quotient graphs, innite trees and, in particular, regular ones. One of our objectives is to highlight the similarities between the two notions, regarding the denitions and also some results without using any cumbersome categorical framework.

In the theory of coverings, a theorem by Norris [START_REF] Norris | Universal covers of graphs: Isomorphism to depth n -1 implies isomorphism to all depths[END_REF] states that two regular rooted trees T x and T y , that dene the universal covering T of a nite undirected graph with p vertices by starting the walks from x and y are isomorphic if their truncations at depth p -1 are isomorphic. Another important theorem by Leighton [START_REF] Leighton | Finite common coverings of graphs[END_REF] states that, if two nite undirected graphs have isomorphic universal coverings, then they have a common nite covering. Its proof is quite difcult. We prove a special case that subsumes the known case of regular graphs [START_REF] Angluin | Finite common coverings of pairs of regular graphs[END_REF].

Weighted graphs. Moreover, we extend the denitions of unfoldings and coverings in the following ways. A directed graphs is weighted if each edge has a weight, a positive integer or the innite cardinal ω. An edge of weight 3 (resp. ω) unfolds into 3 directed edges (resp. countably many) with the same origin. We dene complete unfoldings accordingly, and we obtain regular trees from nite graphs. These trees have nodes of innite degree2 in the case where some edges have weight ω, which generalizes the usual denitions. We call complete unfolding what is usually called the unfolding (this tree is unique up to isomorphism), and we dene as unfolding of a weighted directed graph H a weighted directed graph that lies inbetween H and its complete unfolding. "Inbetween" is formally dened in terms of surjective homomorphisms that are locally bijective as explained above. Each regular rooted tree T is the complete unfolding of a nite unique canonical weighted directed graph, that can be used as a nite description of T . We extend to weighted directed graphs the theorems by Leighton and Norris described above 3 .

We also extend the notion of covering to weighted undirected graphs. In this case, weights in N +  ω are attached to half-edges: an edge that is not a loop has two half-edges and thus two weights. A loop is a half-edge (without any matching opposite half-edge) and has a single weight. Each such graph H has a unique universal covering (unicity is up to isomorphism) that is an innite tree T without root denoted by U C(H). It is formally dened from the unfolding of a directed graph, where p parallel directed edges from a vertex x to y replace a weight p attached to an half-edge incident with x whose matching half-edge is incident with y. It is not from walks as easily as in the case of unweighted graphs.

We call strongly regular a tree T of the form U C(H) for some nite weighted graph H. This means that T yields nitely many regular rooted trees T x , up to isomorphism, by taking its different nodes x as roots. This is a new notion. Each strongly regular tree is the universal covering of a canonical (it is unique up to isomorphism) nite weighted graph of minimal size, and thus, has a nitary description. It can be seen as a kind of minimal factorization. The innite rooted binary tree is regular, but it is not strongly regular after forgetting its root.

Our new denitions and main results 1) We dene and study coverings and unfoldings in close connection by considering them as two instances of the same notion of a locally bijective homomorphism, based on different types of neighbourhood. In both cases we introduce weights on edges. Innite weights yield trees of innite degree having nite descriptions.

2) Our rst main result states that two nite graphs have isomorphic universal coverings if and only if they are coverings of a unique minimal weighted graph. Using weighted graphs is here necessary.

3) Our second main theorem extends that by Norris to universal coverings and to complete unfoldings of nite, weighted, graphs and directed graphs. 4) Our third main theorem extends that by Leighton to complete unfoldings of weighted directed graphs. We give an easy proof of it for coverings of graphs in a special case that subsumes the previously known cases and yields new cases.

5) Finite weighted undirected graphs are dened by matrices in a natural way. Our fourth main theorem extends to them a factorization of the characteristic polynomials of their coverings that is known in the case of nite graphs without weights. Hence, our approach ts nicely in Algebraic Graph Theory.

6) We identify as strongly regular the universal coverings of the nite weighted graphs. They form a proper subclass of regular trees that we study more in [START_REF] Courcelle | Regular and strongly regular innite trees[END_REF].

Summary of the article: Basic denitions are in Section 2. Unfoldings of weighted directed graphs are dened and studied in Section 3. Coverings of weighted undirected graphs are dened and studied in Section 4. We study universal coverings of weighted graphs in Section 5 and we discuss Leighton's Theorem for graphs in Section 6.

Basic denitions

This section reviews notation and some easy lemmas. Denitions for graphs and trees are standard, but we make precise some possibly ambiguous terminological points.

Sets, multisets and weighted sets.

All sets, graphs and trees are nite or countably innite (of cardinality ω).

The cardinality of a set X is denoted by X ∈ Nω. This latter set is equipped with an addition + that is the standard one on N together with the rule ω + x = x + ω = ω for all x in N  ω.

We denote by [p] the set 1,    , p and by N + the set of positive integers.

A weighted set is a pair (X, λ) where X is a set and λ is a mapping X → N +  ω. We call λ(x) the weight of x, and, for Y ⊆ X, we dene 4 λ(Y ) := Σλ(x)  x ∈ Y . A weighted set can be seen as a multiset, where λ(x) is the number of occurrences of x. From a set X, we get the weighted set denoted by (X, 1) where all weights are 1. We dene Set(X, λ) := (x, i)  x ∈ X, i ∈ N + , 1 ≤ i ≤ λ(x) so that λ(X) = Set(X, λ) 

We denote by ] the union of multisets, equivalently of weighted sets: (X, λ) ] (Y, λ ′ ) := (X  Y, λ ′′ ) where λ ′′ (x) is λ(x) + λ ′ (x) if x ∈ X  Y and λ(x) or λ ′ (x) otherwise.

Let (X, λ) and (Y, λ ′ ) be weighted sets. A surjective mapping κ : X → Y is a weighted surjection or a surjection of multisets:

(X, λ) → (Y, λ ′ ) if, for every y ∈ Y , we have λ ′ (y) = λ(κ -1 (y)), hence is the sum of weights of the x's such that κ(x) = y. If X is a set, hence, if λ has value 1 for all x ∈ X, a weighted surjection κ : X → Y satises λ ′ (y) = | | κ -1 (y) | | for every y ∈ Y . Figure 1 illustrates this notion, see Example 2.2(1).
Lemma 2.1: Let (X, λ) and (Y, λ ′ ) be weighted sets.

1) A mapping κ : X → Y is a weighted surjection if and only if there exists a bijection κ ′ :

Set(X, λ) → Set(Y, λ ′ ) such that 5 κ ′ (x, i) = (y, j) implies κ(x) = y
2) If there are weighted surjections κ : (X, λ) → (Y, λ ′ ) and  : Z = (Z, 1) → (Y, λ ′ ), there exists a weighted surjection  : Z = (Z, 1) → (X, λ) such that  ′ = κ ′ •  ′ , where  ′ , κ ′ ,  ′ are 4 For typographical reasons, we use the notation Σλ(x)  x ∈ Y  rather than ∑ x∈Y λ(x) and we will do the same below in Sections 3.1 and 4.2. 5 To simplify notation, we write κ ′ (x, i) instead of κ ′ ((x, i)) and we will do the same in many similar cases. related to , κ,  as in 1). For each triple p, q, r such that κ(p) = (r) = q, we can dene  such that (r) = p.

3) We have λ(X) = λ ′ (Y ) if and only if there exists a set S ⊆ X × Y and a weight function µ on S such that µ(S) = λ(X) = λ ′ (Y ) and for every x ∈ X, λ(x) = µ(S  (x, y)  y ∈ Y ) and similarly, for every y ∈ Y , λ ′ (y) = µ(S  (x, y)  x ∈ X).

Proof:

Let (X, λ) and (Y, λ ′ ) be weighted sets.

1) Assume that we have κ : X → Y and a bijection κ ′ : Set(X, λ) → Set(Y, λ ′ ) as in the statement. Then κ is surjective. For each y ∈ Y , the mapping κ ′ induces a bijection Set(κ -1 (y), λ) → Set(y, λ ′ ), hence λ ′ (y) = λ(κ -1 (y)) Hence, κ is a weighted surjection.

Conversely, let κ : X → Y be a weighted surjection. For each y in Y , since λ ′ (y) = λ(κ -1 (y)), we can dene a bijection: Set(κ -1 (y), λ) → Set(y, λ ′ ). The union of all these bijections denes κ ′ as desired.

2) Let κ and κ ′ be as in 1). We have a bijection

 ′ : Z = Set(Z, 1) → Set(Y, λ ′ ). We dene  ′ : Z = Set(Z, 1) → Set(X, λ) by  ′ := κ ′-1 • ′ ,
from which we get the desired weighted surjection  : (Z, 1) → (X, λ) such that  ′ = κ ′ •  ′ . The condition on p, q, r is straightforward to satisfy.

3) Assume we have λ(X) = λ ′ (Y ). Consider any bijection µ ′ : Set(X, λ) → Set(Y, λ ′ ) Then, we dene µ(x, y) as the cardinality of the set ((x, i), (y, j))  µ ′ (x, i) = (y, j) if it is not empty. We let S ⊆ X × Y be the set of all pairs (x, y) such that µ ′ (x, i) = (y, j) for some i, j. We obtain the desired weight function on S. The converse is clear. 

In Assertion 3), we call S a witness of the equality of weights λ(X) = λ ′ (Y ). If X and Y are disjoint, we can consider it as a bipartite graph whose edges are between X and Y , and are weighted by µ. The weight λ(x) of vertex x is the sum of the weights of its incident edges. See Example 2.2(3). (2) We examplify Assertion [START_REF] Angluin | Local and global properties in networks of processors[END_REF]. Let X, Y, κ, κ ′ be as above and Z := N + . Let  : Z → Y that maps i 7 → u for i = 1,    , 5 and i 7 → v for i > 5. We obtain  ′ that maps i 7 → (a, i) for i = 1, 2, i 7 → (b, i -2) for i = 3, 4, 5, i 7 → (c, i -5) for i = 6,    , 9, and i 7 → (d, i -9) for i > 9 We deduce the weighted surjection  : Z → Y This construction works if we are given p := c, q := v and r := 7 (cf. the last point of Assertion ( 2 If, with the same weighted set X, we take Y consisting of y 1 ,    , y n ,    all of weight ω, then we can take S to consist of (b, y 1 ) of weight 4, (c, y 1 ) of weight 2 and (a, y i ) and (d, y i ) of weight ω for all i. 

(a, i) 7 -→ (u, i) for i = 1, 2, (b, i) 7 -→ (u, i + 2) for i = 1, 2, 3, (c, i) 7 -→ (v, i) for i = 1,    , 4, (d, i) 7 -→ (v, i + 4) for i ≥ 1

Graphs

By a graph we mean an undirected graph, and we call digraph a directed graph, for shortness sake.

A graph is dened as a triple G = (V, E, Inc) where V is the set of vertices, E is the set of edges, and Inc is the incidence relation. The notation e : xy indicates that edge e links vertices x and y, called its ends, equivalently, that (e, x) and (e, y) belong to the set Inc ⊆ E × V . A triple (V, E, Inc) denes a graph if and only if V and E are disjoint, Inc ⊆ E × V , and for each e ∈ E, there are one or two vertices x ∈ V such that (e, x) ∈ Inc.

A pair in Inc is called a half-edge. We write e : xx if e is a loop at x, i.e., incident with x. It is equivalent to a single half-edge. We denote by E(x) the set of edges incident with x, and by N (x) the set y ∈ V  x -y. We have x ∈ N (x) if there is a loop at x. A graph is simple if no two edges have the same set of ends. Hence, it has no two parallel edges. It may have loops, where at most one loop is incident with any vertex.

A walk starting at a vertex x is a possibly innite sequence x 0 , e 1 , x 1 ,    , e n , x n ,    such that x = x 0 , x 1 ,    , x n ,    are vertices and each e i is an edge whose ends are x i-1 and x i . It is a path if the vertices x 0 ,    , x n ,    are pairwise distinct. In both cases, we say that each x i is accessible from x 0 . Its length is the number of edges. A path x 0 ,    , x n denes a cycle if n ≥ 2 and there an edge between x 0 and x n . Its length is n + 1.

A directed graph (a digraph) is dened similarly as a triple G = (V, E, Inc). Its edges are called arcs. An arc e is directed from its tail x to its head y, and we denote this by e : x → y. Its two half-arcs are (x, e) and (e, y), which encodes the direction of e. Hence Inc

⊆ (V × E)  (E × V ). A triple (V, E, Inc) denes a digraph if and only if V and E are disjoint, Inc ⊆ (V × E)  (E × V ),
and for each e ∈ E, there are vertices x, y ∈ V such that (x, e) and (e, y) belong to Inc.

A loop e at x has two half-arcs (x, e) and (e, x). A digraph is simple if, for any x, y, it has no two arcs from x to y. In that case, G can be dened as a pair (V, E) where E ⊆ V × V . To simplify notation, we will also dene such G as a pair (V, E) where an arc in E is dened the pair of a tail and a head.

We denote by E + (x) the set of arcs outgoing from x, and by N + (x) the set of heads of the arcs in E + (x) We have x ∈ N + (x) if there is a loop at x.

A directed walk starting at a vertex x is a possibly innite sequence x 0 , e 1 , x 1 ,    , e n , x n ,    as above such that x = x 0 and e i : x i-1 → x i for each i. Without ambiguity unless it is reduced to the single vertex x 0 , it can be specied as the sequence of arcs e 1 ,    , e n ,    . Its length is its number of arcs. It is a directed path if the vertices x 0 ,    , x n ,    are pairwise distinct. We say that each x i is accessible from x 0 . A digraph is strongly connected if any two vertices are accessible from each other. A directed path x 0 ,    , x n denes a directed cycle if n ≥ 1 and there is an arc x n → x 0 .

A rooted digraph G has a distinguished vertex called the root, denoted by rt G , from which all vertices are accessible by a directed path. We denote by Gx the induced subgraph of G whose vertices are those accessible from x by a directed path. (The study of rooted trees uses this notion with same notation). We dene x as its root.

We denote by U nd(G) the graph underlying a digraph G: each arc e : x → y of G is made into an edge e : xy of U nd(G). Hence, it need not be simple if G is.

We write

V G , E G , E G (x), E + G (x), N + G (x)
, Inc G etc. to specify, if necessary, the relevant graph or digraph G.

For graphs and digraphs, inclusion is denoted by

⊆, i.e. G = (V, E, Inc) ⊆ H = (V ′ , E ′ , Inc ′ ) if and only if V ⊆ V ′ , E ⊆ E ′ and Inc ⊆ Inc ′ . Induced inclusion denoted by ⊆ i holds if, furthermore,
E is the set of edges or arcs of E ′ whose ends, tails and heads are in V . We write then If η : G → H is a homomorphism of graphs or of digraphs, we make G into a labelled graph or digraph G η by equipping each vertex, edge or arc x by the label η(x). Formally, G η = (V, E, Inc, η) Hence, this labelled graph encodes G and η. We will use this notion when H is nite. Other graph labellings will be dened at the relevant places.

G = H[V ]. A homomorphism η : G → H of graphs or of digraphs maps V G to V H , E G to E H , Inc G to
We extend the notion of a homomorphism by allowing "forgetful" operations. A homomorphism U nd(G) → H where G is directed and H is not is also considered as a homomorphism G → H. Similar conventions concern labelled graphs. Denition 2.3: Quotient graphs and digraphs (a) An equivalence relation ∼ on a graph G = (V, E, Inc) is an equivalence relation on V E such that each equivalence class is either a set of vertices or a set of edges, and, if e and e ′ are equivalent edges 6 , then each end of e is equivalent to an end of e ′ .

(b) The quotient graph G ∼ is then dened as

(V  ∼, E ∼, Inc G/∼ ) such that ([e] ∼ , [v] ∼ ) ∈ Inc G/∼ if and only if (e ′ , v ′ ) ∈ Inc for some e ′ ∼ e and v ′ ∼ v.
(c) The denition is similar for a digraph G: we require that if e and f are equivalent arcs, then the tail (resp. the head) of e is equivalent to that of f . The quotient digraph is dened as for graphs.

(d) In both cases, we have a surjective homomorphism η ∼ : G → G ∼ that maps a vertex, an edge or an arc to its equivalence class. An edge e : xy is mapped to a loop in G ∼ if x ∼ y. The same holds for arcs.

Remark 2.4: An equivalence relation ∼ on the vertex set V of G = (V, E, Inc) can be extended to edges or arcs as follows: two edges are equivalent if and only if each end of one is equivalent to some end of the other; two arcs are equivalent if and only if their tails are equivalent and so are their heads.

A notion of quotient graph of a digraph follows then by Denition 2.3. 

Trees

A tree is a nonempty simple connected graph without loops or cycles. We call nodes its vertices. This convention is useful in the frequent case where we discuss simultaneously a graph and a tree constructed from it. The set of nodes of a tree T is denoted by N T . A subtree of a tree T is a connected subgraph, hence, it is a tree. A tree has (locally) nite degree if each node has nite degree. It has bounded degree if the degrees of its nodes are bounded by a same integer.

A rooted tree is a tree T equipped with a distinguished node r called its root. We denote it sometimes by T r to specify simultaneously the root and the underlying undirected tree T In a way depending on r, we direct its edges so that every node is accessible from r by a directed path. If x → y in T r , then y is called a son of x, and x is the (unique) father of y. The depth of a node is its distance to the root (the root has depth 0). The height of a rooted tree is the least upper-bound of the depths of its nodes. A star is a rooted tree of height 1.

Let R be a rooted tree; its root is rt R . By forgetting its root and making its arcs undirected, we get a tree T := U nr(R). Hence, R = T rt R  If x is a node of R, then the digraph Rx is a rooted tree with root x, called the subtree of R issued from x. It is induced on the set of nodes accessible from x by a directed path. If i ∈ N, the truncation at depth i of R, denoted by R  i, is the induced subgraph of R whose nodes are at distance at most i from the root, that is, are accessible from it by a (unique) directed path of length at most i. It is a rooted tree with the same root as R and R  0 is the tree reduced to the root rt R .

A homomorphism of rooted trees: R → R ′ is a homomorphism of directed graphs that maps rt R to rt R ′  A homomorphism from a rooted tree R to a tree T is dened as a homomorphism of trees: U nr(R) → T . Lemma 2.5: An isomorphism of rooted trees η : R → R ′ induces, for each u ∈ N R , an isomorphism: Ru → R ′ η(u) and, in particular, a bijection

N + R (u) → N + R ′ (η(u)) such that Rv ' R ′ η(v) if v ∈ N + R (u)

Unfoldings of directed graphs

Certain abstract programs can be formalized as transition systems that are nite directed graphs with information attached to vertices and arcs. A vertex of the graph is a state of the corresponding transition system. An initial state r is specied. The tree of directed walks starting at r collects all possible computations of the corresponding transition system. It is called its unfolding [START_REF] Arnold | Finite transition systems[END_REF][START_REF] Courcelle | The monadic second-order logic of graphs IX: Machines and their behaviours[END_REF][START_REF] Courcelle | Monadic second-order logic, graph coverings and unfoldings of transition systems[END_REF]. We will consider unfoldings from a graph theoretical point of view, without offering any new application to semantics. We will generalize them and dene unfoldings of digraphs whose arcs have weights. In particular, an arc of weight ω with head y unfolds into countably many arcs whose heads yield y by the unfolding homomorphism. We will obtain a notion of regular tree that generalizes the classical one in that the nodes can have innite outdegrees. These trees are the unfoldings of nite, weighted and rooted digraphs.

In this section, all trees are rooted and thus directed in a canonical way. In [START_REF] Arnold | Finite transition systems[END_REF][START_REF] Courcelle | The monadic second-order logic of graphs IX: Machines and their behaviours[END_REF][START_REF] Courcelle | Monadic second-order logic, graph coverings and unfoldings of transition systems[END_REF] the unfolding of a rooted digraph G is what we will call its complete unfolding. We will call unfolding of such a digraph G a rooted digraph that lies inbetween, via surjective homomorphisms, the digraph G and its complete unfolding, denoted by Unf (G). This terminology is thus similar to that concerning coverings and universal coverings.

The main contributions of this section are the use of possibly innite weights, the decidablility of isomorphism in Theorem 3.14, and two theorems similar to those by Norris and Leighton for universal coverings of nite undirected graphs, see Theorems 3.20 and 3.22.

Equality of trees and digraphs will be understood in the strict sense: same nodes or vertices, and same arcs. Equality via an isomorphism is specied explicitely in statements and proofs, and denoted by '.

Weighted directed graphs and their unfoldings

We will equip digraphs with weights in N +  ω We recall from Section 2.2 that a digraph can be dened as a pair (V, E) where each arc e is an ordered pair of vertices. A weighted digraph is a triple G = (V, E, λ) such that (V, E) is a digraph whose set of arcs E is weighted, that is, equipped with a weight function λ : E → N +  ω We denote by E + (u) the weighted set (E + (u), λ) and by N + (u) the weighted set (N + (u), λ ′ ) such that λ ′ (v) = Σλ(e)  e : u → v.

A digraph7 is a weighted digraph whose arcs have all the weight 1.

A weighted digraph is simple or rooted if the underlying digraph is. If x is a vertex of a weighted digraph G, then Gx (cf. Section 2.2) is a rooted and weighted digraph with root x. If G is strongly connected, the digraphs Gx have all the same vertices and arcs as G.

In the special case where G is simple digraph, then E + (u) = (E + (u), 1), N + (u) = (N + (u), 1) and the head mapping is a bijection E + (u) → N + (u). 

We can handle parallel arcs by means of weights. That is, an arc (x,y) of weight λ(x, y) > 1 encodes λ(x, y) parallel arcs from x to y.

Denition 3.2: Unfolding

Let H and G be rooted and weighted digraphs. (a) A surjective homomorphism η : G → H is an unfolding of H if it induces a weighted surjection

E G → E H  In particular, if u ∈ V G and η(u) = x, then η induces a weighted surjection E + G (u) → E + H (x) If G and H are simple digraphs, then η induces a bijection E + G (u) → E + H (x) and a bijection N + G (u) → N + H (x).
We will also say that G is an unfolding of H or that H unfolds into G. From the accessibility condition in the denition of a rooted digraph, unfoldings only concern connected graphs. They are called op-brations by Boldi and Vigna [START_REF] Boldi | Fibrations of graphs[END_REF].

(b) An unfolding G → H is complete if G is a rooted tree without weights (equivalently, all weights are 1). We will also say that G is a complete unfolding of H or that H unfolds completely into G.

Examples 3.3: (1) A loop of weight 1 (resp. 2) unfolds completely into an innite directed path (resp. into the innite binary rooted tree).

(2) An arc x → y of weight ω such that x is taken as root unfolds (not completely) into any nite star, where at least one arc has weight ω. It unfolds completely into a star S ω , i.e., any tree whose root has ω sons that are leaves 8 . If in addition, there is a loop y → y of weight 1, this rooted and weighted digraph unfolds completely into the union of ω innite directed paths with the same origin, that are otherwise disjoint.

Proposition 3.4: (1) If η : G → H and κ : H → K are unfoldings, then κ•η is an unfolding G → K.
(2) If η : G → H is an unfolding, u ∈ V G and x = η(u), then η is an unfolding9 Gu → Hx.

Proof:

(1) The composition κ•η induces a weighted surjection E G → E K as κ and η do the same E H → E K and E G → E H respectively. This observation proves the assertion.

(2) Clear from Denition 3.2. 

The following theorem implies that every rooted and weighted digraph H has, up to isomorphism, a unique complete unfolding. Theorem 3.5: Let H be a rooted and weighted digraph.

1) H has a complete unfolding.

2) If  : T → H is a complete unfolding, then:

(U) For every unfolding κ : G → H, there is a complete unfolding η :

T → G such that  = κ • η.
3) Any two complete unfoldings of H are isomorphic. 4) If  : T → H is an unfolding such that Condition (U) holds, then T is a rooted tree, hence a complete unfolding of H.

Properties 2) and 4) show that the complete unfoldings of H are characterized by a universal property in the sense of Category Theory. One can speak of the complete unfolding of H, well-dened up to isomorphism. The following notion helps to approximate, level by level, a complete unfolding. The height of a rooted tree is the least upper-bound of the distances of its nodes to the root. Denition 3.6: Depth-limited unfoldings.

Let A be a rooted tree of height at most i (cf. Section 2.3) and H be a rooted and weighted digraph. An i-unfolding η : A → H is a homomorphism (it is not necessarily surjective) satisfying the following condition:

For every node u of A at distance at most i -1 from the root, if η(u) = x and e is an arc of H with tail x, then

| | η -1 (e)  E + A (u) | | = λ H (e) 
The complete unfolding of a rooted unweighted digraph H can be constructed as the tree of nite walks starting from the root. As weights in digraphs represent parallel arcs, this construction must be adapted. This is the purpose of the following denition, that replaces parallel arcs with sets of parallel ones.

Denition 3.7: The expansion of a weighted digraph.

Let H = (V, E, λ) be a weighted digraph. Its expansion is the digraph Exp(H) = (V, Set(E, λ)) having the arc (e, i) : x → y if e : x → y in H and (e, i) ∈ Set(E, λ). (The mapping Set is dened in Section 2.1) The digraph Exp(H) is innite if some arc has weight ω, and/or, of course, if V is innite. If H has a root, then Exp(H) has the same root.

We now prove Theorem 3.5.

Proof:

Let H be a rooted and weighted digraph.

1) The rooted digraph Exp(H) is an unfolding of H, and we denote by  the corresponding homomorphism Exp(H) → H. By Proposition 3.4, we need only construct a complete unfolding T of Exp(H). We dene it as the tree of directed walks in Exp(H) that start from rt H , the common root of Exp(H) and H. The father of a node (e 1 ,    , e p ) is (e 1 ,    , e p-1 ).

Let  : T → Exp(H) map (e 1 ,    , e p ) to the head of e p ; if p = 0, then (e 1 ,    , e p ) is the empty walk, mapped to rt H ; the arc from (e 1 ,    , e p-1 ) to (e 1 ,    , e p ) is mapped to e p . We say that this arc of T is of type e p .

Then  is a complete unfolding T → Exp(H) and  := • yields a complete unfolding T → H. We will denote T by Unf (H). Note that Unf (H) is a concrete tree made of walks in Exp(H).

If H is a rooted tree, then Exp(H) ' H and  and  are isomorphisms as one checks easily.

2) We let  : Unf (H) → H be the particular complete unfolding constructed in 1) and κ : G → H be any unfolding.

By induction on i, we construct for each i, an i-unfolding

η i : Unf (H)  i → G such that κ • η i is the restriction of  to Unf (H)  i (
the restriction of Unf (H) to nodes at distance at most i from the root) in such a way that η i+1 extends η i . The union of the mappings η i will be a complete unfolding

η : Unf (H) → G such that  = κ • η.
We construct η i+1 from η i as follows. Let u = (e 1 ,    , e i ) ∈ N T i be mapped to w ∈ V G by η i . There is a weighted surjection µ u :

N + Unf (H) (u) → N + G (w) such that κ • µ u is the restriction of  to N + Unf (H) (u). Its existence follows from Lemma 1.1(2), as N + Unf (H) (u) is a set, equivalently, the weighted set N + Unf (H) (u) = (N + Unf (H) (u), 1)
. Then, we let η i+1 be the union of η i and all such mappings µ u for all nodes u of Unf (H) at depth i.

To prove 3) and to complete the proof of 2), we let κ : G → H be a complete unfolding, hence, G is a tree. Then, the complete unfolding η : Unf (H) → G is an isomorphism. Hence, any two complete unfoldings of H are isomorphic and 2) holds for any complete unfolding  of H 4) Let  : T → H be an unfolding such that Condition (U) holds. Let G be a complete unfolding of H. There is an unfolding  : T → G. Since G is a tree, T is also a tree, hence a complete unfolding of H. 

We will reserve the notation Unf (H) to the complete unfolding dened as a tree of walks in H. It is dened in [START_REF] Arnold | Finite transition systems[END_REF][START_REF] Courcelle | The monadic second-order logic of graphs IX: Machines and their behaviours[END_REF][START_REF] Courcelle | Monadic second-order logic, graph coverings and unfoldings of transition systems[END_REF], but not characterized by a universality property.

Complete unfoldings and regular trees

The notion of an innite regular tree is important in applications to semantics, in particular because the complete unfolding of a nite transition system is regular [START_REF] Arnold | Finite transition systems[END_REF][START_REF] Courcelle | Fundamental properties of innite trees[END_REF][START_REF] Courcelle | Recursive applicative program schemes[END_REF], and more generally for the monadic second-order logic of innite structures, see [START_REF] Courcelle | The monadic second-order logic of graphs IX: Machines and their behaviours[END_REF][START_REF] Courcelle | Monadic second-order logic, graph coverings and unfoldings of transition systems[END_REF]. We will consider regular trees that are complete unfoldings of nite digraphs.

A graph, a digraph or a tree can have labels attached to its vertices, nodes, edges or arcs.

Denition 3.8: Regular trees.

A rooted, possibly labelled, tree T is regular 10 if it has nitely many subtrees T x (inheriting the possible labels of T ), up to isomorphism, which we will denote by u.t.i., that is, if the set of isomorphism classes [T x] '  x ∈ N T  is nite. In the latter case, its cardinality is the regularity index of T, denoted by Ind(T ). If T is regular, each subtree T x is regular of no larger index because (T x)y = T y for y ≤ T x (which means that x is on the directed path from the root to y).  Every nite tree is regular. A rooted tree of height 1 (a star) is regular of index 2. We will prove that the complete unfolding of a nite, rooted and weighted digraph H, that may have innite weights, is regular of index at most V H  and has a canonical "factorization" in terms of a nite weighted digraph analoguous to the minimal automaton of a regular language.

Let G be a weighted digraph. Let ≈ be the equivalence relation 11 on V G such that x ≈ y if and only if Unf (Gx) ' Unf (Gy) According to the denitions of Section 1.2, the quotient H := G ≈ is the simple digraph dened as follows:

V H := [x] ≈  x ∈ V G  and E H := ([x] ≈ , [y] ≈ )  G has an arc x → y. If G is rooted, we take rt H := [rt G ] ≈  We have a surjective homomorphism η : G → H We now dene weights on the arcs of H. If e is an arc x → y of G, we dene λ ′ G (e) := Σλ G (f )  f : x → z is an arc of G for some z ≈ y. Lemma 3.9: Let x, x ′ be vertices of G such that x ≈ x ′ .
(1) If there is an arc x → y for some y, then there is one

x ′ → y ′ such that y ′ ≈ y. ( 2
) If e is an arc x → y, e ′ is an arc x ′ → y ′ such that y ′ ≈ y, then λ ′ G (e) = λ ′ G (e ′ ) Proof: (1) Assume x ≈ x ′ . Let  : Unf (Gx) → Gx by the unfolding homomorphism, mapping the root x of Unf (Gx) to x, and similarly  ′ : Unf (Gx ′ ) → Gx ′ mapping the root x ′ of Unf (Gx ′ ) to x ′ . Let µ be an isomorphism Unf (Gx) ' Unf (Gx ′ ) It maps x to x ′ .
Let e be an arc x → y of G. There is

u in Unf (Gx) such that (u) = y and x → u in Unf (Gx) Let y ′ :=  ′ (µ(u)) We have x ′ → µ(u), hence an arc x ′ → y ′ in G.
We have Unf (Gy) ' Unf (Gx)u ' Unf (Gx ′ )µ(u) ' Unf (Gy ′ ) Hence, y ′ ≈ y.

(2) If e is an arc x → y of G and with the same notation as in (1), we observe that, since  is an unfolding, λ ′ G (e) is the number of sons u of the root of the tree Unf (Gx) such that Unf (Gx)u ' Unf (Gy) Then, if e ′ is an arc x ′ → y ′ , we have similarly that λ ′ G (e ′ ) is the number of sons u ′ of the root of the tree

Unf (Gx ′ ) such that Unf (Gx ′ )u ′ ' Unf (Gy ′ ) Since y ′ ≈ y, we have λ ′ G (e) = λ ′ G (e ′ )  Denition 3.10:
The canonical quotient of a rooted and weighted digraph.

Let G be a rooted and weighted digraph and H := G ≈ as above. The mapping η such that η(x)

:= [x] ≈ if x ∈ V G and η(e) := ([x] ≈ , [y] ≈ ) if e is an arc x → y of G is a homomorphism G → H that is surjective by Lemma 3.9(1).
We dene a weight function on

H by λ H ([x] ≈ , [y] ≈ ) := λ ′ G (e)
for any arc e : x → z of G such that z ≈ y. It is well-dened by Lemma 3.9 [START_REF] Angluin | Local and global properties in networks of processors[END_REF].

Furthermore, if G is vertex-labelled, then x ≈ y implies that x and y have same label. The quotient digraph H := G ≈ is vertex-labelled and the homomorphism η : G → H preserves labels.

We dene the size G of a digraph G as

V G  + E G .  Proposition 3.11: (1) The homomorphism η : G → G ≈ is an unfolding. ( 2
)
If G is nite, then G ≈ is, up to isomorphism, the unique rooted and weighted digraph of minimal size of which G is an unfolding. We now consider the case where R is a regular tree. Theorem 3.14 will prove that ≈ and G ≈ are computable if G is nite. Theorem 3.13: (1) A rooted tree T is regular of index at most p if it is the complete unfolding of a nite, rooted and weighted digraph having p vertices.

(2) Conversely, a regular tree T is the complete unfolding of a unique rooted and weighted simple digraph having Ind(T ) vertices.

(3) If η : T → H is a complete unfolding of a rooted and weighted digraph having p vertices (p ∈ N + ), then the labelled rooted tree T η (where each node u is labelled by η(u)) is regular of index at most p.

Proof:

(1) Let η : T = Unf (H) → H be the unfolding homomorphism where H is a rooted and weighted digraph having p vertices. If u, v ∈ N T and η(u) = η(v) = x, then T u ' T v because these two trees are complete unfoldings of Hx by Proposition 3.4 [START_REF] Angluin | Local and global properties in networks of processors[END_REF]. It follows that T is regular and its index is at most the number of vertices of H.

(2) Conversely, let T be a regular tree of index p. Let ≈ be the equivalence relation on N T such that u ≈ v if and only if T u ' T v We have T u ' Unf (T u) The quotient construction of Denition 3.10 shows that T is the complete unfolding of the nite, rooted and weighted digraph T  ≈, that has p vertices.

(3) Easy extension of [START_REF] Abello | On the complexity and combinatorics of covering nite complexes[END_REF]. 

Finite, rooted and weighted digraphs can be used as nite descriptions of regular trees. Although an arc of weight p ∈ N + can be replaced (cf. Denition 3.7) by p parallel arcs and a loop of weight q ∈ N + by q loops, the use of weights gives more concise descriptions. Furthermore, the weight ω makes it possible to describe trees of innite degree in nitary ways, by means of nite arc-labelled digraphs 12 . The following result shows that this description is effective. Theorem 3.14: Given a nite weighted digraph H and two vertices x, y ∈ V H , one can decide whether Unf (Hx) ' Unf (Hy).

We need a few technical denitions and lemmas. Denition 3.15: Equivalent weighted sets.

Let R be an equivalence relation on a set V and X, Y ⊆ V (a) Let X = (X, λ) and Y = (Y, λ ′ ) be weighted sets. We write X ∼ Y (mod R) if:

(C) For every equivalence class C of R, we have λ(C  X) = λ ′ (C  Y ).
Equivalently, for every x ∈ X, there is

y ∈ Y such that λ([x] R  X) = λ ′ ([y] R  Y ) and (x, y) ∈ R,
and similarly, for every y ∈ Y , there is x ∈ X such that (x, y) satises the same property. This is an equivalence relation.

Condition (C) implies that λ(X) = λ ′ (Y ) (b) A witness of the equivalence X ∼ Y (mod R) is a set S ⊆ X × Y with weight function µ, that is the (disjoint) union of witnesses of the weight equalities λ(C  X) = λ ′ (C  Y ) for all equivalence classes C of R, (cf. Lemma 2.1(3). 
We say that an equivalence relation R renes an equivalence relation R ′ on the same set if each class of R ′ is a union of classes of R. This is written R ⊆ R ′ , by considering equivalence relations as sets of pairs. In the following two lemmas, V, R, X and Y are as in the previous denition.

Lemma 3.16: If X ∼ Y (mod R) and R ⊆ R ′ , then X ∼ Y (mod R ′ ). Proof: Each class C ′ of R ′ is the union of (disjoint) classes C 1 , C 2 ,    of R. Hence, λ(C ′  X) = λ(C 1  X) + λ(C 2  X) +   
and similarly for Y . The result follows.  Lemma 3.17: Assume that X ∼ Y (mod R). Let U and W be sets, and κ and η be weighted surjections 13 , respectively U → X and W → Y . There is a bijection `: U → W such that (κ(u), η(`(u)) ∈ R for all u in U . Furthermore, for any u 0 ∈ U and w 0 ∈ W such that (κ(u 0 ), η(w 0 )) ∈ R, one can nd `as above such that `(u 0 ) = w 0 

Proof:

We have a bijection  : Set(X, λ) → Set(Y, λ ′ ) such that 14 (x, i) = (y, j) implies (x, y) ∈ R, and bijections κ ′ : U → Set(X, λ) and η ′ :

W → Set(Y, λ ′ ). We dene `:= η ′-1 •  • κ ′ 
For proving the last assertion, we choose  such that (κ(u 0 ), i) = (η(w 0 ), j) for some i, j. 

The bijection `is uniquely dened if λ([x] R  X) = λ ′ ([y] R  Y ) = 1
for all x ∈ X and y ∈ Y , but not otherwise. We now prove Theorem 3.14.

Proof:

Let H be a nite weighted digraph 15 and ≈ be the equivalence relation on V H such that x ≈ y if and only if Unf (Hx) ' Unf (Hy). We recall from Section 2 that N + H (x) is the set of heads of the arcs with tail x and that N + H (x) := (N + H (x), η) where η(y) is the sum of the weights λ H (e) of the arcs e : x → y (cf. Denition 3.2, H may have parallel arcs). Proof : We consider (x, y) ∈ R, and we let κ : T → Hx and κ ′ : T ′ → Hy be the unfolding homomorphisms where T := Unf (Hx) and T ′ := Unf (Hy)

For each i, we construct by induction an isomorphism η i :

T  i → T ′  i such that (κ(u), κ ′ (η i (u)
)) ∈ R for every node u of T  i, and η i+1 extends η i  The common extension of these isomorphisms will be an isomorphism T → T ′ , proving that x ≈ y.

We let η 0 map rt T to rt T ′ . We have (x, y) = (κ(rt T ), κ ′ (η 0 (rt T ))) ∈ R, as was to be veried. We now dene η i+1 extending η i . Consider v in T  (i + 1) at depth i + 1 and its father u. Then w := η i (u) is a node of T ′  i Furthermore κ induces a weighted surjection N + T (u) → N + H (κ(u)), and similarly, κ ′ induces a weighted surjection N + T (w) → N + H (κ ′ (w)) By the inductive property of η i , we have (κ(u), κ ′ (w)) ∈ R. Hence, by Property (E), we have

N + H (κ(u)) ∼ N + H (κ ′ (u))(mod R) By Lemma 3.17, there is a bijection `u : N + T (u) → N + T (w) such that (κ(s), κ ′ (`u(s)) ∈ R for each s in N + T (u) (s is in T  (i + 1)
). We dene η i+1 (s) := `u(s) for every son s of u in T . 13 A weighted surjection of a set X onto a weighted set is well-dened by considering that each element of X has weight 1. 14 We recall that we write γ(x, i) for γ((x, i)) 15 It is not necessarily rooted.

We do that for all nodes v at depth i + 1 in T . We obtain the desired extension with the inductive property (t, η i+1 (t)) ∈ R for every node t of T  (i + 1).  There are nitely many equivalence relations R on V H . For each of them, one can check if it satises Property (E) and contains the pair (x, y). Then x ≈ y if and only if one of them has these two properties.



The following algorithm is similar to the minimization of nite deterministic automata. It will help to prove Theorem 3.20.

Algorithm 3.18: Deciding the isomorphism of complete unfoldings.

Input: A nite weighted digraph 16 H. Output: The equivalence relation ≈ on V H such that x ≈ y if and only if Unf (Hx) ' Unf (Hy).

Method: We dene a decreasing17 sequence of equivalence relations R i , i ≥ 0 on V H as follows:

R 0 = V H × V H ; R i+1 = R i  (x, y)  N + H (x) ∼ N + H (y) (mod R i ) We have R i+1 = R i
for some i := i max , and we output R i as the desired result. Proposition 3.19: Algorithm 3.18 is correct and terminates with i max ≤ V H  -1

Proof:

Let R be the intersection of the relations R i . It is clear that if R i+1 = R i , then R i+2 = R i+1 etc... so that, R i = R. This guarantees termination.

Each step such that R i+1 6 = R i splits at least one equivalence class of R i . Such a splitting cannot be done more than V H  -1 times.

We now prove the correctness, i.e., that ≈ = R. We prove that ≈ ⊆ R i for all i. This is clear for i The following result is similar to a theorem by Norris [START_REF] Norris | Universal covers of graphs: Isomorphism to depth n -1 implies isomorphism to all depths[END_REF] about universal coverings that we presented in the introduction and that we will generalize in Section 4 to weighted graphs. See [START_REF] Courcelle | Regular and strongly regular innite trees[END_REF], it implies that, for every regular tree, there is a rst-order sentence using the generalized quantier "there exists ω elements x that satisfy..." of which it is the unique model that is a rooted tree. Theorem 3.20: Let H be a nite weighted digraph with p vertices. If x, y ∈ V H , then: Unf (Hx)  (p -1) ' Unf (Hy)  (p -1) implies Unf (Hx) ' Unf (Hy).

= 0. Assume now ≈ ⊆ R i . If x ≈ y, then N + H (x) ∼ N + H (y) (mod ≈), hence N + H (x) ∼ N + H (y) (mod R i )

Proof:

We use the relations R i of Algorithm 3.18. We know by Proposition 3.19 that ≈ = R p-1 .

Claim: If Unf (Hx)  (p -1) ' Unf (Hy)  (p -1), then (x, y) ∈ R p-1 .
Proof : By using induction, we prove that for every i:

Unf (Hx)  i ' Unf (Hy)  i implies (x, y) ∈ R i . If i = 0, this fact holds because (x, y) ∈ R 0 for all x, y
We prove the case i + 1 by assuming that we have an isomorphism  : Unf (Hx)  (i + 1) → Unf (Hy)  (i + 1). Hence Unf (Hx)  i ' Unf (Hy)  i and (x, y) ∈ R i by the induction hypothesis.

We now check that N + H (x) ∼ N + H (y) (mod R i ) in order to obtain that (x, y) ∈ R i+1 . Let η : Unf (Hx) → Hx and η ′ : Unf (Hy) → Hy be complete unfoldings. We have η(rt Unf (H/x) ) = x and η ′ (rt Unf (H/y) ) = y

For each son u of rt Unf (H/x) ,  denes an isomorphism: This argument is correct only if Unf (Hx) and Unf (Hy) have nite degree, by using König's Lemma, as in the proof of Lemma 2.7 of [START_REF] Krebs | Universal covers, color renement, and two-variable counting logic: Lower bounds for the depth[END_REF].

Unf (Hx)u  i → Unf (Hy)(u)  i, where (u) is a son of rt Unf (H/y)  But Unf (Hx)u = Unf (Hη(u)) and Unf (Hy)(u) = Unf (Hη ′ ((u))) Hence (η(u), η ′ ((u))) ∈ R i by induction. Then N + H (x) is the set of such η(u) and N + H (y) is that of such η ′ ((u)) By counting occurrences, we obtain N + H (x) ∼ N + H (y)(mod R i ) Hence, (x, y) ∈ R i+1   If Unf (Hx)  (p -
However, this implication is false for trees with nodes of innite degree. Let T be the union of the

nite paths 0 → (1, i) → (2, i) → • • • → (i, i) for all i ∈ N + , and T ′ be T together with the innite path 0 → 1 → 2 → • • • → i →    . They are not isomorphic, but T  i ' T ′  i for each i. Theorem 3.
14 is used for proving Theorem 3.20. To prove its Claim 2, we cannot use König's Lemma because the trees Unf (Hx) and Unf (Hy) need not have nite degree. Instead, we construct a sequence of isomorphisms:

η i : Unf (Hx)  i → Unf (Hy)  i such that η i+1 extends η i 
Their common extension yields an isomorphism: Unf (Hx) → Unf (Hy). 

The following theorem is similar to that of Leighton about coverings ( [START_REF] Leighton | Finite common coverings of graphs[END_REF], see below Theorem 4.10), and much easier to prove. We dene ≈ as the equivalence relation on

V G  V H such that x ≈ y if and only if Unf ((G  H)x) ' Unf ((G  H)y)), where Unf ((G  H)x) = Unf (Gx) if x ∈ V G
and similarly for H as G and H are disjoint.

For helping to understand the technical details, we rst present the proof for the special case where there are no two distinct nodes u, v in T with same father, and such that T u ' T v. This fact implies that all arcs in G and H have weight 1. In such a case: (*) if u ∈ N T , the relation T v ' Unf (Gy) denes by Lemma 2.4 a bijection between the sons v of u in T and the vertices y in N + G ((u)). A similar fact holds for H with the vertices y in

N + H (η(u))
We dene a digraph L as follows. Its set of vertices is V L := (x, y)  x ∈ V G , y ∈ V H and Unf (Gx) ' Unf (Hy). For each (x, y) ∈ V L , the relation ≈ denes, by Fact (*) above, a bijection between N + G (x) and N + H (y)We dene in L an arc (x, y) → (x ′ , y ′ ) (of weight 1) if x ′ ∈ N + G (x) and y ′ ∈ N + H (y) (and of course x ′ ≈ y ′ ). We now dene K := L(rt G , rt H ). It is a nite and rooted digraph. The projection π 1 such that π 1 (x, y) := x is an unfolding K → G. The other projection is an unfolding K → H.

We now consider the general case. The construction is similar, but the denition of the arcs (x, y) → (x ′ , y ′ ) of L is more complicated because the relation ≈ is not necessarily a bijection between N + G (x) and N + H (y) We dene V L as above. For each (x, y) ∈ V L , we have N + G (x) ∼ N + H (y)(mod ≈) by Lemma 2.4. We choose a witness (S x,y , µ x,y ) of N + G (x) ∼ N + H (y)(mod ≈), cf. Denition 3.15(b). We dene in L an arc (x, y) → (x ′ , y ′ ) of weight µ x,y (x ′ , y ′ ) for each (x ′ , y ′ ) in S x,y . We now dene K := L(rt G , rt H ). It is rooted and weighted with at most V G .V H  vertices.

Claim: K is an unfolding of G, and, similarly, of H.

Proof of claim: Let π map a vertex (x, y) of K to the vertex x of G, and an arc (x, y) → (x ′ , y ′ ) to the arc x → x ′ of G. We make a few observations.

(1) If (x, y) ∈ V L and xx ′ is an arc of G, there is an arc (x, y) → (x ′ , y ′ ) in L. If (x, y) ∈ V K then (x ′ , y ′ ) and the arc (x, y) → (x ′ , y ′ ) are in K that is a subgraph of L.

(2) If x is a vertex in G, there is a directed path from rt G to x and, by (1), a directed path in L from the root (rt G , rt H ) to (x, y) ∈ V L for some y ∈ V H . All vertices and arcs of this path are in K.

It follows that π is a surjective homomorphism: K → G We now check Denition 3.2. We verify the following condition.

(**) For every (x, y) ∈ V K and x ′ ∈ N + G (x), we have:

λ G (x, x ′ ) = Σλ K ((x, y), (x ′ , y ′ ))  (x ′ , y ′ ) ∈ V K 
By the denition of K, λ K ((x, y), (x ′ , y ′ )) = µ x,y (x ′ , y ′ ), and the pairs (x ′ , y ′ ) are in S x,y . The weighted set (S x,y , µ x,y ) is chosen so that λ G (x, x ′ ) = Σµ x,y (x ′ , y ′ )  (x ′ , y ′ ) ∈ S x,y  This proves (**), the claim and point 3).

3) =⇒1) Assume that  : T → G and η : T → H are complete unfoldings. Let ≈ be the equivalence relation on N T such that u ≈ v if and only if T u ' T v. We dene M as the weighted graph T  ≈, cf. Denition 3.11 and the proof of Theorem 3.12. There are unfoldings:  ′ : G → M and η ′ : H → M . We omit details.

The decidability follows from Theorem 3.19.  Remarks 3.23: In the proof of 2) =⇒3), T is a complete unfolding of K by Theorem 3.5. Note however that in this proof, K is not dened in a unique way, in particular because the weighted relations (S x,y , µ x,y ) are not uniquely dened. It is however in the special case we rst considered.

Coverings

In this section and the next two ones, we will consider undirected graphs, simply called graphs, and their coverings. We recall from Section 2.1 that a graph G is dened as a triple (V, E, Inc) where the elements of Inc (a subset of E × V ) are its half-edges. This description allows graphs with parallel edges and loops. An edge e is a loop at a vertex x if and only if (e, x) ∈ Inc and there is no pair (e, y) in Inc such that y 6 = x. We denote by Inc(x) the set of half-edges (e, x) for some e ∈ E. Its cardinality is the degree of x, where a loop at x counts for one. We will use trees (undirected and without root) and rooted trees, in particular the regular trees considered in the previous section. Trees and graphs may be labelled.

The main contributions of this section are the denition of weighted graphs, that can be seen as graph interpretations of degree matrices. We extend coverings to weighted graphs. If two nite graphs have a common (nite) covering, they cover a common (nite) weighted graph (Theorem 4.10). Regarding characteristic polynomials, we obtain an extension of a known factorization result (Section 4.3). We postpone to Section 5 the study of universal coverings of weighted graphs.

As in Section 3, equality of trees and graphs is understood in the strict sense: same nodes or vertices, and same edges or arcs. Equality up to isomorphism is specied explicitely and denoted by '.

Coverings of graphs: denitions and known results

We mainly review known denitions and facts from [START_REF] Angluin | Local and global properties in networks of processors[END_REF][START_REF] Angluin | Finite common coverings of pairs of regular graphs[END_REF][START_REF] Bodlaender | The classication of coverings of processor networks[END_REF][START_REF] Bodlaender | Simulation of large networks on smaller networks[END_REF][START_REF] Fiala | Locally constrained graph homomorphisms -structure, complexity, and applications[END_REF][START_REF] Krebs | Universal covers, color renement, and two-variable counting logic: Lower bounds for the depth[END_REF][START_REF] Leighton | Finite common coverings of graphs[END_REF][START_REF] Norris | Universal covers of graphs: Isomorphism to depth n -1 implies isomorphism to all depths[END_REF]. Our main reference for all assertions is [START_REF] Fiala | Locally constrained graph homomorphisms -structure, complexity, and applications[END_REF] by Fiala and Kratochvíl.

We dene the adjacency matrix A G of a nite graph G such that V G = [p] := 1,    , p for some p as follows: A G [x, y] = A G [y, x] is the number of edges between x and y and A G [x, x] is the number of loops at x.

 : G → H is a surjective homomorphism such that, if (x) = y, then  denes a bijection E G (x) → E H (y) We will also say that G is a covering of H. (b) Let G, H be nite, V G = [p] and V H = [q].
A surjective mapping  : V G → V H can be represented by a p × q-matrix B γ such that B γ [i, j] := if (i) = j then 1 else 0. Each row of this matrix has a unique 1 and each column has at least one 1. Then,  denes a covering if and only if

A G B γ = B γ A H . 
An edge covers a loop incident to a single vertex. More generally, a k-regular graph, i.e. such that all vertices have degree k, covers k loops incident to a single vertex.

Proposition 4.2: Let  : G → H be a covering. (1) If  : H → K is a covering, then  •  : G → K is a covering. (2) If G and H are nite and H is connected, then, either  is an isomorphism or V G  > V H  and then, V G   V H  = Inc G   Inc H 
and this number is a positive integer.

(3) If H is a tree and G is connected, then G is a tree and  is an isomorphism.

Proof:

Assertion (2) is due to Reidemeister (see [START_REF] Bodlaender | The classication of coverings of processor networks[END_REF][START_REF] Bodlaender | Simulation of large networks on smaller networks[END_REF][START_REF] Reidemeister | Einführung in die kombinatorische Topologie[END_REF]). Here is a proof sketch (cf. Section 2.1 in [START_REF] Fiala | Locally constrained graph homomorphisms -structure, complexity, and applications[END_REF]).

Let T be a spanning tree of H. It does not include the loops that are irrelevant to connectedness. Then,  -1 (E T ) is a set of edges of G. By the denition of a covering, it is the union of k pairwise disjoint trees, all isomorphic to T by . This union includes all vertices, hence V G   V H  = k

We now prove that Inc G   Inc H  = k Consider the edges e of G such that (e) is a loop at x in H. Such an edge may link two vertices in different connected component of G. We have the pair ((e), x) in Inc H and a single pair of the form (e, u) such that (u) = x in each connected component of G. Hence, there are k such edges e.

Consider now the edges e of G such that (e) : xy is not a loop in H. We have ((e), x) and ((e), y) in Inc H . Each e yields exactly two pairs (e, u) and (e, v) in Inc G such that (u) = x and (v) = y. There are exactly 2k such pairs (e, u) and (e ′ , v) in Inc G . Hence, Inc G   Inc H  = k

(3) This is known from [START_REF] Fiala | Locally constrained graph homomorphisms -structure, complexity, and applications[END_REF][START_REF] Reidemeister | Einführung in die kombinatorische Topologie[END_REF] if H is nite. Assume now that H is innite. Consider as in (2) the edges of  -1 (E H ) of G. They form a union of spanning trees T of G. There are no other edges in G. As G is connected, it is a tree.  Denition 4.3: Degree matrix (a) For every nite graph G, there is a unique partition (B 1 ,    , B p ) of V G having a minimum number of classes, such that for every i, j ∈ [p], every vertex x in B i has the same number of neighbours, say r i,j , in B j . It is called the degree (renement) partition. It can be computed in polynomial time [START_REF] Berkholz | Tight lower and upper bounds for the complexity of canonical colour renement[END_REF].

(b) Let  : V G → [p] maps a vertex x to the integer i such that x ∈ B i . We call  a good indexing of V G . The numbers r i,j can be organized into a p × p matrix M G,α such that and M G,α [i, j] = r i,j  It is called the degree (renement) matrix of G. This matrix may not be symmetric.  ] (b) Every connected graph H has a universal covering constructed as follows. For a vertex x of H, we dene U C(H, x) as the rooted tree of all nite walks in H that start at x and do not use a same edge (including a loop) twice in a row. The tree U nr(U C(H, x)) is obtained by forgetting the root of U C(H, x) and its orientation. It is a covering of H, hence a universal one. We have U nr(U C(H, x)) ' U nr(U C(H, y)) for any two vertices x and y ( [START_REF] Fiala | Locally constrained graph homomorphisms -structure, complexity, and applications[END_REF], Section 4.2). Examples are given below.  Examples 4.7: (1) An edge is the universal covering of a single loop. A path with 4 vertices is that of an edge with a loop at one of its ends.


(2) If H consists of two parallel edges, then U nr(U C(H, x)) is a biinnite path, i.e., the union of two innite paths originating from a same node. (A biinnite path is somehow isomorphic to Z). Equivalently, it is the unique tree u.t.i. (up to isomorphism) whose nodes have all degree 2. It is also the universal covering of two loops at a same vertex or of any cycle.

(3) The universal covering of a connected k-regular graph is the innite tree whose nodes have all degree k. This is clear from the construction recalled in Denition 4.6(b). 

We recall that if u is a node of a tree T , then T u is the rooted tree obtained by taking u as the root.

Proposition 4.8: Let H, H ′ be graphs.

(1) If  : T → H is a universal covering and u ∈ N T , then T u ' U C(H, (u)).

(2) If there an isomorphism of H to H ′ maps x to y, then U C(H, x) is isomorphic to U C(H ′ , y).

Proof:

(1) We will prove below a generalization of this fact for weighted graphs.

(2) This is clear from the descriptions of U C(H, x) and U C(H ′ , y) in terms of walks.  By Assertion (1) and Denition 4.6(b), all universal coverings of H are isomorphic. One can speak of the universal covering of H, denoted 18

by U C(H).

Remark 4.9: The converse to Assertion (2) does not hold when H = H ′ . Take for a counter-example the union of the two graphs of Figure 4 with an edge between the two vertices marked a, that we will call x and y. Then U C(H, x) ' U C(H, y) but there exists no automorphism of H that maps x to y. 

The relevance to distributed computing can be stated as follows: if x and y are two nodes of a network represented by a graph H and U C(H, x) ' U C(H, y), then, no computation in H (following certain rules, see [START_REF] Angluin | Local and global properties in networks of processors[END_REF]) can distinguish x from y. It follows that an election algorithm that would select x would also select y, hence would not be correct. (i) G and H have a common nite covering, (ii) G and H have isomorphic universal coverings, (iii) M G,α = M H,β for some good indexings  and  of V G and V H .

The implication (iii)=⇒(i) has a difcult proof by Leighton in [START_REF] Leighton | Finite common coverings of graphs[END_REF]. We will prove in Theorem 6.1 below is a special case of it from which follows that of regular graphs, known from Angluin and Gardiner [START_REF] Angluin | Finite common coverings of pairs of regular graphs[END_REF].

If G and H have the same number of vertices, them (iii) implies that they are fractionally isomorphic by Theorem 6.5.1 of the book [START_REF] Scheinerman | Fractional Graph Theory[END_REF]. We will not develop this aspect in the present article.

We will interpret a degree matrix M G,α and a good indexing  of a graph G as a covering  : G → M where M is a nite weighted graph. Furthermore, we will allow innite weights and obtain universal coverings that are trees of innite degree, as in Section 3 for unfoldings. Denition 4.11: Equivalences on graphs that yield coverings.

We recall from Section 1 that an equivalence relation ∼ on a graph G = (V, E, Inc) is an equivalence relation on V  E such that each equivalence class is a set of vertices or of edges, and, if e and e ′ are equivalent edges, then each end of e is equivalent to an end of e ′ . The quotient graph is then dened as

G ∼:= (V  ∼, E ∼, Inc G/∼ ) such that ([e] ∼ , [v] ∼ ) ∈ Inc G/∼ if and only if (e ′ , v ′ ) ∈ Inc G for some e ′ ∼ e and v ′ ∼ v.
We say that such an equivalence ∼ is strong if, whenever x and x ′ are equivalent vertices, it denes a bijection between E(x) and E(x ′ ).  Proposition 4.12: (1) If ∼ is a strong equivalence on a graph G, then the surjection  :

V  E → (V  ∼)  (E ∼) that maps x to its equivalence class [x] ∼ is a covering G → G ∼.
(2) Every connected graph H is isomorphic to T  ∼ where T is its universal covering and ∼ is a strong equivalence relation on T .

Proof:

(1) The proof is straightforward.

(2) We let  : T → H be a universal covering where T = (N, E, Inc). We dene x ∼ y for x, y ∈ N  E if and only if (x) = (y). Then T  ∼ is isomorphic to H. 

Quotients of trees will be studied in Sections 5.2 and 6.

Coverings of weighted graphs

We extend to weighted graphs the notion of covering. The two graphs of Example 4.4 cover a same weighted graph but no same graph. The case of nite weighted graphs will be of particular interest, because they provide us with nite descriptions of certain regular trees. Let H and G be a weighted graphs. A covering  : G → H is a surjective homomorphism of unweighted graphs such that, if x ∈ V G , (x) = y and e ∈ E H (y), then:

λ H (e, y) = Σλ G (e ′ , x)  e ′ ∈ E G (x), (e ′ ) = e, or equivalently,  induces a weighted surjection (Inc G (x), λ G ) → (Inc H (y), λ H )
We will say that G is a covering of H. (2) If H is a simple graph, then G is a graph and the condition implies that  is injective on each set Inc G (x), whence bijective: we get the notion of covering of Section 4.1.

(3) Each graph G covers the weighted graph W (G). 

Coverings of nite weighted graphs, even having innite weights, can also be expressed in terms of weight matrices (as for graphs in terms of adjacency matrices, cf. Denition 4.1).

Let G and H be nite weighted graphs and  : V G → V H be surjective, where V G = [p] and V H = [q] This mapping is represented by the matrix B α (as in Denition 4.1) such that:

B α [i, j] := if (i) = j then 1 else 0.
The following proposition is straightforward from the denition. For dening the product of two matrices, we use the rules ω + x = ω for every x, ωx = ω if x > 0 and ω0 = 0 We need no substractions.

Proposition 4.16:

A homomorphism  : G → H is a covering if and only if M G B α = B α M H .
Remark 4.17: Here is a method to build a graph G that covers a nite or innite weighted graph H. It is similar to the construction of the proof of Proposition 4.2 [START_REF] Angluin | Local and global properties in networks of processors[END_REF]. Given H = (V, E, Inc, λ), we construct G = (V ′ , E ′ , Inc ′ ), as follows (it is unweighted).

We choose a set V ′ and a surjective mapping  : V ′ → V . For each x ∈ V ′ and (e, (x)) ∈ Inc, we create λ(e, (x)) (yet abstract) half-edges incident with x, dened as pairs ((e, i), x) for i = 1, 2,    , λ(e, (x)). In this way, we have dened Inc ′ . We let  map ((e, i), x) to (e, (x))

We choose a partial matching M on Inc ′ satisfying the following property:

A pair in M is of the form (((e, i), y),((e, j), z)) such that y 6 = z and e : (y) -(z) is an edge of H, and this pair denes an edge f in G; we dene (f ) := e If ((e, i), y) is not matched in M , then e is a loop in H incident with (y); ((e, i), y) is a loop f of G and dene (f ) := e There are numerical constraints on V ′ and , as we will see in Theorem 4.24. Remark 4.19: If two disjoint weighted graphs are coverings of H, then, their union is a covering of H. If  : G → H is a covering and G is connected, then H is connected because  maps every path in G to a walk in H. If H is not connected, then G is the union of (disjoint) coverings of its connected components. It follows that we need only consider connected coverings of connected weighted graphs.

Examples 4.20: 1) The complete bipartite graph K 3,4 (with 3+4 vertices) covers H consisting of one edge whose half-edges have weights 4 and 3. Although H is a tree, Proposition 4.2(3) does not hold. Proposition 4.2(2) does not either: V G  need not be a multiple of V H  when G is a covering of a weighted graph H.

2) A graph G consisting of 3 parallel edges covers the graph W (G) consisting of an edge whose two half-edges have weight 3, that itself covers a loop of weight 3.

3) If H has a loop of weight p at a vertex x, then H is covered by the weighted graph built as follows: we remove the loop at x, obtaining thus H ′ ; we take the union of H ′ and a disjoint copy of it where x ′ is the copy of x and we add one edge between x and x ′ whose two half-edges have weight p.

4) The two graphs of Figure 4, Example 4.4 cover both the weighted graph H shown in Figure 5.

5) The graph G consisting of two vertices, x and y, an edge e : xy and loops f and g at x and y with weights λ(e, x) = 3, λ(e, y) = 2, λ(f, x) = 4 and λ(g, y) = 5, covers H consisting of a single vertex with a loop of weight 7.

The Kronecker product of a weighted graph H by an edge is a weighted bipartite graph, whose universal covering is that of H. We will use this notion in Section 6.

Denition 4.21: Kronecker product by an edge.

Let H be a weighted graph. Its Kronecker (or categorical) product by K 2 (a single edge) is the weighted bipartite graph H×K 2 dened as follows. Its vertex set is

V H×K 2 := V H ×1, 2, partitioned into (V H × 1, V H × 2).
For each edge e of H between x and y 6 = x, H × K 2 we have the edge e x,y : (x, 1) -(y, 2) (and also e y,x : (y, 1) -(x, 2)) A loop e at x yields a unique non-loop edge e x,x : (x, 1) -(x, 2) The weight λ G (e x,y , (x, i)) is λ H (e, x) for i = 1, 2.  Lemma 4.22: Let G and H be weighted graphs.

(1) There is a covering

H × K 2 → H (2) From a covering  : H → G one can dene a covering  ′ : H × K 2 → G × K 2 .
Proof:

(1) The mapping π: (x, i) 7 -→ x, e x,y 7 -→ e is a covering: H × K 2 → H. If H is connected and bipartite, then H ×K 2 has two connected components, that are isomorphic. Each of them is a covering of H.

(2) From  : H → G, we dene  ′ : H × K 2 → G × K 2 by  ′ (x, i) := ((x), i) and  ′ (e x,y ) := (e) α(x),α(y) . 

In particular, every (nite) weighted graph is covered by a (nite) weighted bipartite graph. Then we have:

B α =         1 0 1 0 0 1 0 1 0 1         , M G =         0 1 1 1 1 1 0 1 1 1 1 1 0 0 0 1 1 0 0 0 1 1 0 0 0         and M G B α =         1 3 1 3 2 0 2 0 2 0         = B α M H where (1) = (2) = 1 and (3) = (4) = (5) = 2. 
The following theorem is stated without proof in [START_REF] Leighton | Finite common coverings of graphs[END_REF] but is essential in this article (which proves a part of Theorem 4.10 ; see also [START_REF] Fiala | Locally constrained graph homomorphisms -structure, complexity, and applications[END_REF], Section 4.1). Theorem 4.24: Given a nite weighted graph H with nite weights, one can decide if it is covered by a nite unweighted graph G. If this is the case, one can construct G loop-free.

Proof:

Let H = ([p], E, Inc, λ) be a nite weighted graph with nite weights. We rst assume that H has no loops.

Assume that  : G → H is a covering where G is a nite graph.

For each i, let

w i := | |  -1 (i) | |
. Let e i,j : ij be an edge of H, with i < j. Let m i,j = λ(e i,j , i) and m j,i = λ(e i,j , j). We have

| |  -1 (e i,j ) | | = m i,j w i = m j,i w j  Consider the system Σ H of
equations of the form m i,j x i = m j,i x j , with one equation for each edge e i,j . It is satised by the numbers (w 1 ,    , w p ). This system may have no solution. We give an example after the proof.

Claim 1: If Σ H has a solution (w 1 ,    , w p ) in positive integers, then this p-tuple is equal to ( | |  -1 (1) | | ,    , | |  -1 (p) | | ) for some nite covering  of H by a graph G.
Proof : We dene G from (w 1 ,    , w p ). Its vertices are the pairs (i, s) where i ∈ [p] = V and s ∈ [w i ] For an edge e i,j of H, we let m := m i,j w i = m j,i w j  We dene as follows m edges f 1 ,    , f m between the vertices (i, s) and (j, s ′ ) where s ∈ [w i ] and s ′ ∈ [w j ].

We partition [m] into pairwise disjoint intervals 19 ;

[m] = I 1  I 2  • • •  I w i ,
where all intervals I q have size m i,j , and also

[m] = J 1  J 2  • • •  J w j ,
where all intervals J q have size m j,i  For k ∈ [m], we dene an edge f i,j,k between (i, s) and (j, s ′ ) if and only if k ∈ I s  J s ′  We dene (f i,j,k ) := e i,j  Hence,  is a surjective homomorphism.

For each vertex (i, s), if e i,j is an edge in H, then the edges f i,j,k such that (f i,j,k ) := e i,j are those such that k ∈ I s  J s ′ for some s ′  There are m i,j such edges. Similarly for each vertex (j, s ′ ) such that e i,j is an edge in H (hence where i < j) , there are m j,i edges f i,j,k such that (f i,j,k ) := e i,j : they are those such that k ∈ I s  J s ′ for some s Hence, G is a nite covering of H.  Claim 2: A system Σ H has a solution in positive integers if and only if it has one in rational numbers. This is decidable and a solution in positive integers can be computed if there is one. If H is a tree, then Σ H has a solution.

Proof : We rst decide if Σ H has a solution in real numbers. We eliminate unknowns one by one.

To eliminate an unknown x, we list the equations where it occurs: say ax = by, cx = dz,    , ex = f u. Then, any solution must satisfy ba -1 y = dc -1 z = • • • = f e -1 u. We replace the equations containing x by the new equations ba

-1 y = dc -1 z = • • • = f e -1 u
The new system has one less unknown and has a solution if and only if Σ H has one. From it, we get the value of x. We may obtain two equations concerning the same variables, say gy = hz, and g ′ y = h ′ z, where g, h, g ′ , h ′ are positive rational numbers. We have no solution if gh ′ 6 = g ′ h: we can stop the construction and report a negative answer. Otherwise, we discard one of these two equations.

If there is a solution, there is one in positive rational numbers. To obtain one in positive integers, it sufces to multiply all its components by the least common multiple of the denominators.

If H is a tree, then, at each step, we can eliminate an unknown that belongs to a single equation, equivalently, that corresponds to a leaf. Hence, this step does not create any new equation. The resulting system still corresponds to a tree. We continue in the same way and we get a solution.  We now complete the main proof for weighted graphs with loops. Loops do not create constraints: if we add to a weighted graph L a loop of weight q incident with a vertex x, and if a covering  of L by a graph G has been found, then we need only add q loops to G, incident to each vertex in  -1 (x). We do that for all loops of the given graph H and we get a covering as wanted.

If we replace the obtained graph G by G × K 2 of Lemma 4.22, we obtain a loop-free graph that covers G hence also H.  Example 4.25: Let H be the cycle C 3 with vertices 1,2,3 and weights on its half-edges such that we get the equations 2x 1 = 3x 2 , 4x 2 = 3x 3 , x 3 = 5x 1 . This system has no solution in positive integers. This means that H is not covered by any nite graph. It is covered by the innite tree described as follows. Its set of nodes is N 1  N 2  N 3 where N 1 , N 2 , N 3 are innite and pairwise disjoint; each node in N 1 has 2 neighbours in N 2 and 5 in N 3 , each node in N 2 has 3 neighbours in N 1 and 4 in N 3 , and each node in N 3 has 1 neighbour in N 1 and 3 in N 3  This tree does not cover any nite graph. 

The following corollary is a key fact in the proof of Theorem 4.10 by Leighton [START_REF] Leighton | Finite common coverings of graphs[END_REF]. It is an immediate consequence of the proof of Theorem 4.24. If H is a graph, then the corresponding p-tuple is (1,. . . ,1) by Proposition 4.2(2).

-tuple (n 1 ,    , n p ) ∈ (N + ) p such that (kn 1 ,    , kn p )  k ∈ N +  is the set of p-tuples ( | |  -1 (1) | | ,    , | |  -1 (p) | | ) such that  : G -→ H is a covering where G is a nite graph.

Characteristic polynomials

It is known that if G is a covering of H where G and H are nite graphs, then the characteristic polynomial of H is a factor of that of G ( [START_REF] Fiala | Locally constrained graph homomorphisms -structure, complexity, and applications[END_REF], Theorem 4). We extend this result to nite weighted graphs.

Denitions 4.27: Characteristic polynomials.

(a) The characteristic polynomial P M of a p × p matrix M with coefcients in a ring with multiplicative unit, typically Z,R or C, is dened as the determinant of the matrix M -xI p where I p is the p × p (diagonal) unity matrix, denoted by det(M -xI p ). It is a polynomial in x of degree p. The characteristic polynomial P G of a nite graph G is dened as that of its adjacency matrix A G that is symmetric with coefcients in N. The coefcients of P G are in Z.

(b) We dene the characteristic polynomial of a nite weighted graph H with nite weights as P H := det(M H -xI p ) where M H is its weight matrix, having coefcients in N. For an example, if H is as in Example 4.4, Remark 4.15(3) and Example 4.20(4), then

P H = -x(2 -x) -6 = x 2 -2x -6
Theorem 4.28: If G and H are nite weighted graphs with nite weights and G covers H, then P H is a factor of P G .

Proof:

Immediate consequence of Proposition 4.16 and the following one. 

The representation of a surjective map  : [q] -→ [p] by a q × p matrix B α is in Denition 4.1(b).

Proposition 4.29: Let M and N be, respectively, q × q and p × p matrices over a ring with multiplicative unit. Let  : [q] -→ [p] be a surjective mapping. If M B α = B α N , then P N is a factor of P M .

Proof:

We transform the matrix M -xI q by row and column operations into a matrix M ′′ such that det(M -xI q ) = det(M ′′ ).

We do that in such a way that M ′′ has the block structure

[ N -xI p R 0 S ]  It follows that det(M - xI q ) = det(N -xI p ) det(S), hence P M = P N  det(S).
We can organize M in such a way that i ∈ (i) for each i ∈ [p]. This means that i is the smallest element of each set (i). For each such i, we add to the i-th column of M, all its j-th columns, for j ∈ (i), j > i.

We obtain a matrix M ′ with same determinant as M -xI q  Since M B α = B α N, the rst p elements of the j-th line of M ′ are the same as those of the (j)-th one . By substracting the i-th line from each j-th line, for all i ∈ [p], j ∈ (i), j > i, we get a matrix M ′′ of the desired form, with same determinant as M -xI q and M ′′ . This concludes the proof.  Example 4.30: (1) For the matrices N = M H and M = M G of Example 4.23, we have q = 5, p = 2, and: 20 that:

M -xI 5 =         -x 1 1 1 1 1 -x 1 0 0 1 1 -x 1 1 1 0 1 -x 0 1 0 1 0 -x         , M ′ =         1 -x 3 1 1 1 2 -x 1 0 0 1 -x 3 -x 1 1 2 -x 1 -x 0 2 -x 1 0 -x         , M ′′ =         1 -x 3 1 1 1 2 -x 1 0 0 0 0 -1 -x 0 0 0 0 0 -x 0 0 0 0 0 -x         = [ N -xI 2 R 0 S ] so that det(M -xI 5 ) = det(N -xI 2 ) det(S) One can check
det(N -xI 2 ) = (x + 2)(x -3), det(S) = -x 2 (x + 1)
and

det(M -xI 5 ) = -x 2 (x + 1)(x + 2)(x -3) (2)
If G is a weighted graph with p vertices, then P G×K 2 (x) = (-1) p P G (x)P G (-x) where G × K 2 is the Kronecker product (Denition 4.21). This fact can be proved by using the algorithm of the previous proposition.

Universal coverings of weighted graphs

We will construct the universal covering of a weighted graph from an unfolding of an associated weighted and rooted digraph. This construction will enlighten the relationships between universal coverings and complete unfoldings. It extends the description given for graphs in Denition 4.6(2), based on walks that do not traverse an edge twice in a row. Because of weights, this construction is no longer convenient.

Furthermore, we will use in a straighforward manner the results of Section 3.2 about complete unfoldings, in particular our adaptation of Norris's Theorem (Theorem 3.20), to obtain a corresponding result about universal coverings of nite weighted graphs. We will also dene strongly regular graphs, a new notion linked with coverings of nite weighted graphs. A covering of weighted graphs  : G → H is universal if G is a tree (without weights), which implies that H is connected. We also say that G is a universal covering of H.

Universal coverings of weighted graphs

We will prove that any two universal coverings of a connected and weighted graph are isomorphic. We rst give some examples.

Examples 5.2: 1) An innite tree whose nodes all have degree p where 1 < p ≤ ω is a universal covering of a loop of weight p > 1 All nodes of the tree are mapped to the vertex at the loop. It is also a universal covering of an edge whose half-edges both have weight p.

2) A tree such that every node of degree 3 is adjacent to a node of degree 4 and vice-versa is a universal covering of K 3,4 and also, of an edge whose half-edges have weights 4 and 3.

3) A tree consisting of one node adjacent to ω leaves is a universal covering of an edge whose half-edges have weights 1 and ω.

4) A universal covering  of the graph H consisting of a path x-y -z with a loop at x, all weights being 1, is the path z 1y 1x 1x 2y 2z 2 with (x 1 ) = (x 2 ) = x, (y 1 ) = (y 2 ) = y and (z 1 ) = (z 2 ) = z. 5) A biinnite path (cf. Example 4.9(2)), is a universal covering of the following weighted graphs:

(a) a cycle (in particular two parallel edges) whose half-edges have weight 1, or an edge with both half-edges of weight 2, (b) the weighted graph H as in 4) except that the weight of the half-edge at z is 2, (c) one loop of weight 2 or two loops of weight 1 incident to a same vertex, (d) a path P with ends x and y 6 = x such that, either x and y have both a loop of weight 1, or x has a loop of weight 1 and the half-edge (f, y) on 21 P has weight 2, or the half-edges (e, x) and (f, y) on P has both weight 2. 

We will describe a construction of a universal covering for weighted graphs and prove a characterization similar to that of complete unfoldings of Theorem 3.5, that entails unicity, u.t.i., of universal coverings.

Denition 5.3: The symmetric weighted digraph of a weighted graph and its expansion.

(a) Let H = (V, E, Inc, λ) be a connected and weighted graph, for which we x a linear order ≤ on V . The associated symmetric weighted digraph is Sym(H) := (V, E ′ , λ ′ ) dened as follows. For each edge e : xy of E, we dene the following arcs of E ′ and their weights: if x < y (e is not a loop), we dene 22 e + : x → y and e -: y → x, of respective weights λ(e, x) and λ(e, y), if x = y (e is a loop), we dene e `: x → x of weight λ(e, x) (b) We dene ES(H) as the expansion of Sym(H) (cf. Denition 3.7). It is the (unweighted) digraph (V, E ′′ ) dened as follows, directly from H. For each edge e : xy of E, we dene the following arcs of E ′′ :

(e + , i) : x → y if x < y, for i ∈ N + , 1 ≤ i ≤ λ(e, x), (e -, i) : y → x if x < y, for i ∈ N + , 1 ≤ i ≤ λ(e, y), (e `, i) : x → x if x = y (e is a loop) for i ∈ N + , 1 ≤ i ≤ λ(e, x)
The digraphs Sym(H) and ES(H) are strongly connected as H is connected.

(c) Let ι : ES(H) → H be the homomorphism 23 that is the identity on V H = V ES(H) and is dened as follows on the arcs of ES(H): ι(e + , i) := e, ι(e -, i) := e and ι(e `, i) := e For each x ∈ V H , it induces a weighted surjection of the set E + ES(H) (x) onto (Inc H (x), λ H )  Any vertex x of the weighted digraph Sym(H) can be taken as a root. We obtain a rooted digraph denoted by Sym(H) x , similarly as for T x , Section 2.3. The accessibility condition of Section 2 is satised because Sym(H) is strongly connected. We dene ES(H) x in the same way. 21 We mean that f belongs to the path P . 22 The purpose of the order on vertices is to differenciate without ambiguity e + from e -. 23 A homomorphism can map a digraph to a graph, cf. Section 2. Example 5.4: Figure 6 shows a graph H and the digraph Sym(H) dened from the ordering x < y < z. The drawing of the loop h of H recalls that it counts for 1 in the degree of x. For readability, we denote in Sym(H) the arc e + by e, the arc e -by e (and similarly for f and g), and the loop h by h. As H has no weights, ie all weights are 1, ES(H) = Sym(H), with the arc (e + , 1) identied with e + , and similarly for the other arcs.

Figure 7 shows the rooted tree Unf (Sym(H) x )  3 that consists in the rst three levels of Unf (Sym(H) x ). Its root is denoted by x.  For dening the universal covering of a weighted graph, we generalize, by the following denition, the condition of Denition 4.6(2) requiring that the walks dening nodes do not traverse twice in a row a same edge or loop. That is, we eliminate from Unf (ES(H) x ) the walks that violate this condition.

Denition 5.5: The pruning operation.

(a) Let H be a weighted graph and x ∈ V H . Then, Unf (ES(H) x ) is a rooted tree, whose root is denoted by x rather than by rt Unf (ES(H) x ) . The pruned rooted tree P r(Unf (ES(H) x )) is obtained by deleting nodes and arcs as follows: The following theorem is similar to Theorem 3.5. We recall that U nr forgets the root and removes the orientations of a rooted tree.

Theorem 5.7: Let H be a connected and weighted graph.

1) For each x ∈ V H , the tree U nr(U C(H, x)) is a universal covering of H.

2) If µ : T → H is a universal covering, then:

(C) For every covering κ : G → H, where G is connected and weighted, there is a universal covering η : T → G such that µ = κ • η.

3) Any two universal coverings of H are isomorphic. 4) If µ : T → H is a covering such that Condition (C) holds, then T is a tree, hence a universal covering of H. We let W be the (unrooted tree) U nr(P r(Unf (ES(H) x ))). We claim that it is a universal covering of H, with covering homomorphism induced by ι •  First, we prove that  is surjective on P r(Unf (ES(H) x )) Let y ∈ V H . There is a path P in H from x to y. There is a path P ′ in Unf (ES(H) x ) from x to some y ′ whose image by ι •  is y. This path neither uses an arc of type (f + , i) after one of type (f -, j) or vice-versa, nor an arc of type (f `, i), otherwise P would have an edge occurring twice or a loop.

Hence, the path P ′ is not deleted by the pruning operation, so that y ′ is in P r(Unf (ES(H) x )) and yields y by ι • . Similarly, any edge e of H is on a path P from x with corresponding path P ′ in Unf (ES(H) x ) and e is the image under ι •  of an arc in P ′ . Hence, ι •  is surjective on P r(Unf (ES(H) x )) Next, we check the condition of Denition 4.14. Let u be a node of P r(Unf (ES(H) x )) Let e be an edge of H incident to (u) The arcs of Unf (ES(H) x ) incident to u whose image by  is e are as follows, according to different cases.

Case 1: u is the root. There are λ H (e) such arcs. They are all of type (e + , i) (cf. the proof of Theorem 3.5 [START_REF] Abello | On the complexity and combinatorics of covering nite complexes[END_REF] for the notion of type), or all of type (e -, i), or all of type (e `, i) and they are in P r(Unf (ES(H) x )) Hence λ H (e, (u)) = e ′  e ′ ∈ E T (u), ι • (e ′ ) = e  Case 2: u is not the root and is the head of an arc of type (f + , i) or (f -, i) or (f `, i) where f 6 = e. We are exactly as in Case 1.

Case 3: u is not the root and is the head of an arc of type (e + , i) for some i. The arcs of Unf (ES(H) x ) we are considering are the λ H (e, (u)) arcs of types (e -, j) together with the arc with head u. Hence, we seem to have one arc too much. But the pruning operation eliminates the arc (e -, 1) Hence, we still have λ

H (e, (u)) = e ′  e ′ ∈ E T (u), ι • (e ′ ) = e 
Case 4: As in Case 3 with an incoming arc of type (e -, i) or (e `, i) for some i. The argument is as in Case 3.

Hence, ι •  induces (via the restriction to P r(Unf (ES(H) x ))) a covering from the tree W := U nr(U C(H, x)) to H.

2) We prove the assertion for W := U nr(U C(H, x)) and ι •  : W → H as in 1). We let κ : G → H be a covering where G is connected and weighted. Let x ′ ∈ V G be such that κ(x ′ ) = x For each i, we construct an i-covering η i : U C(H, x)  i → G x , i.e., a homomorphism such that Condition (S') holds for all nodes of U C(H, x)  i at depth less than i. This is similar to the notion of i-unfolding in Denition 3.6. We want that η i+1 extends η i and that κ • η i is the restriction of ι •  to U C(H, x)  i For i = 0, we dene η 0 (x) := x ′  We now dene η i+1 extending η i . Let u be at depth i We have a weighted surjection from the set E W (u) to (Inc H (x), λ H ) and a weighted surjection (Inc G (η i (u)), λ G ) to (Inc H (x), λ H ). Lemma 2.1 [START_REF] Angluin | Local and global properties in networks of processors[END_REF] shows that we have a weighted surjection  from E W (u) to (Inc G (η i (u)), λ G ) such that κ •  = ι •  on E W (u) Furthermore, we can choose  such that (e) = η i (e) where e is the arc in U C(H, x)) with head η i (u) (The node u is not the root of U C(H, x)) If v is the head of an arc with tail u of type (f

+ , i) or (f -, i), then (v) is the end of f different from η i (u); if the type is (f `, i), then (v) := η i (u)
We dene η i+1 as η i extended by all such mappings . The union of the mappings η i yields a universal covering

η : W → G, where W := U nr(U C(H, x)).
If G is a tree, then η is an isomorphism U C(H, x) → G by Proposition 4.2(3). This completes the proof of 2) and proves 3). If R is a rooted tree, we dene Sym(R) by adding to R an "up-going" arc v → u for each arc u → v. It is nothing but Sym(U nr(R)) constructed by Denition 5.3 with all weights equal to 1 and a linear order such that x < y if x → y in R. We obtain a strongly connected rooted digraph with root rt R . See Figure 11 for an example.

e : u → v is of the form (f + , i) ∈ E ES(H) (this means that we have f : (u) -(v) in H and (u) < (v)), then,  ′ (e) := (f -, 1),
if it is of the form (f -, i), then,  ′ (e) := (f + , 1), if it is of the form (f `, i), then,  ′ (e) := (f `, 1)

These "up-going" arcs restablish some arcs deleted by pruning, but not the deleted subtrees.

Then  ′ : Sym(U C(H, x)) → ES(H) x is an unfolding. It follows from Theorem 3.5 that

Unf (Sym(U C(H, x))) is a complete unfolding of ES(H) x . Hence, Unf (Sym(U C(H, x))) ' Unf (Sym(ES(H) x ))  (N): if v ∼ v ′ ,
w is a neighbour of v, and v has exactly p (p may be ω) neighbours equivalent to w, then v ′ has exactly p neighbours equivalent to w, then T is a universal covering of the weighted graph H := T  ∼ dened as follows:

-

V H := N T  ∼, -E H contains the edge e : [v] ∼ -[w] ∼ if
(v) = [v] ∼ and (e) is the edge [v] ∼ -[w] ∼ if e : v -w is a universal covering of H. If v ∼ w, then the edge [v] ∼ -[w] ∼ is a loop. 
Corollary 5.14: Every tree is a universal covering of a weighted graph.

Proof:

If T is a tree and ≈ is the equivalence relation on N T dened by x ≈ y if and only if T x ' T y , then H := T  ≈ is a weighted graph and T is a universal covering of it. 

Universal coverings of nite weighted graphs

We will call strongly regular the universal coverings of nite weighted graphs. These regular trees have not been previously identied to our knowledge. We rst extend a result proved by Norris [START_REF] Krebs | Universal covers, color renement, and two-variable counting logic: Lower bounds for the depth[END_REF][START_REF] Norris | Universal covers of graphs: Isomorphism to depth n -1 implies isomorphism to all depths[END_REF] for graphs without weights. Our proof will use Theorem 3.20, the similar result for complete unfoldings, by means of Theorem 5.12.

Theorem 5.15: Let T be a universal covering of a nite weighted graph H with p vertices. For every two nodes x, y of T , we have T x ' T y if and only if T x  (p -1) ' T y  (p -1).

Proof:

We prove the property for T x := U C(H, x) and T y := U C(H, y). The "only if " direction is clear. As a consequence of Theorem 5.15, we obtain in [START_REF] Courcelle | Regular and strongly regular innite trees[END_REF] a rst-order denability result for the strongly regular trees U C(H) similar to that for regular trees following from Theorem 3.20. Denition 5.17: Regular unrooted trees.

We recall that the subtrees of a (labelled) rooted tree R are the (labelled) rooted trees Rx for x ∈ N R . Their nodes are those of R accessible from x. By Denition 3.8, a rooted (labelled) tree R is regular if the set of isomorphism classes [Rx] ' for x ∈ N R is nite. In that case, its cardinality is the regularity index Ind(R) of R.

A (labelled) tree T without root is regular if the rooted (labelled) tree T x is regular for some x ∈ N T . Proposition 5.18: If a (labelled) tree T is regular, then the rooted (labelled) trees T y are regular for all y ∈ N T .

Proof:

Let T x be regular for x ∈ N T . If y is a neighbour of x, then the subtrees of T y are T y , T y x and the subtrees T x z for z  ∈ x, y Hence there are nitely many up to isomorphism. If y is at distance n of x, there is a path xz 1 -• • •z n-1y and each rooted tree T z 1 ,    , T z n-1 , T y is regular by the rst observation. 

We may have Ind(T y ) > Ind(T x ), as shown in Example 5.21.

Denition 5.19: Strongly regular trees.

A possibly labelled tree T is strongly regular if it has nitely many associated rooted trees T

x , u.t.i, that is, if the set [T x ] '  x ∈ N T  is nite. 
We will prove that a strongly regular tree is regular. This is not an immediate consequence of the denition as we do not require that any of the trees T x is regular. However, all are.

Example 5.20: The rooted tree P such that N P := N and x ≤ P y if and only if y ≤ x is an innite path P . It is regular, hence, the tree U nr(P ) is regular. The rooted trees U nr(P ) x are all regular but pairwise non isomorphic. Hence, U nr(P ) is not strongly regular. Proposition 5.21: Let H be a nite, connected and weighted graph.

(1) Its universal coverings are strongly regular.

(2) For each x ∈ V H the rooted tree U C(H, x) is regular.

Proof:

(1) If η: T → H is a universal covering, then for each node x of T , we have T x ' U C(H, η(x)) by Corollary 5.8 [START_REF] Abello | On the complexity and combinatorics of covering nite complexes[END_REF]. Hence, T is strongly regular.

(2) Let x ∈ V H . The rooted tree Unf (ES(H) x ) from which we get U C(H, x) by pruning is regular, but this is not enough to conclude.

Let : Unf (ES(H) x ) → Sym(H) be the homomorphism that is the composition of the unfolding  : Unf (ES(H) x ) → ES(H) x and  : ES(H) → Sym(H) where  is the identity on vertices.

Let u and u ′ be nodes of U C(H, x), hence of Unf (ES(H) x ), that are not the root. Let e : v → u and e ′ : v ′ → u ′ be the arcs of Unf (ES(H) x ) with heads u and u ′ . If (e) = (e ′ ) then (u) = (u ′ ) and we have P r(Unf (ES(H) x ))u ' P r(Unf (ES(H) x ))u ′  Note that  maps Unf (ES(H) x ) to Sym(H). We may have e = (f + , i) and e ′ = (f + , j) so that (e) = (e ′ ) = f + .

It follows that U C(H, x)u ' U C(H, x)u ′ and that the subtrees of U C(H, x) are U C(H, x) itself and those associated as above with the arcs of Sym(H). Hence, there are at most 1 + 2 E H  subtrees u.t.i, and U C(H, x) is regular.  Theorem 5.22: A tree T is strongly regular if and only if it is the universal covering of a nite, connected and weighted graph if and only if it is the universal covering of such a graph without loops.

Proof:

If T is the universal covering of a nite, connected and weighted graph, then it is strongly regular by Proposition 5.21.

Conversely, let T be a strongly regular tree. Let ∼ be the equivalence relation on N T such that x ∼ y if and only if T x ' T y . This equivalence relation satises Condition (N) of Proposition 5.13 and has nitely many classes. Hence, by this proposition, T is a universal covering of the nite weighted graph H := T  ∼.

Finally we show how to replace H by H ′ without loops. A loop of weight p arises in H if a node has p neighbours equivalent to it. To avoid loops, we dene on T a proper 2-coloring. We dene ∼ ′ such that x ∼ ′ y if and only if T x ' T y and x and y have the same color. Then T is a universal covering of the nite weighted graph H ′ := T  ∼ ′ that has no loop 27 .  Examples 5.23: 1) Let T consist of a biinnite path B (cf. Example 4.9(2)), where each node x has, in addition, an incident pendent edge xx ′ for some new node x ′ . The rooted trees T x for x ∈ N B are all isomorphic, and so are the trees T x ′ . The quotient graph is the edge [x] ∼ -[x ′ ] ∼ together with a loop at [x] ∼ of weight 2, that yields trees isomorphic to T x . The two other half-edges have weight 1.

2) For the tree of Example 4.20(1), we get an edge with weights 3 and 4.

Remark 5.24: 1) Finite weighted graphs can be used as nite descriptions of strongly regular trees, even of innite degree. The construction of Theorem 5.22 denes a minimal and canonical one.

2) By Theorem 5.22, a strongly regular tree is the universal covering of a nite minimal weighted graph H. It is not necessarily that of a nite graph G, otherwise such a graph G would cover H, and Example 4.25 shows that this may be not possible. A k-regular graph has all its vertices of degree k. It may have loops. A loop contributes 1 to the degree of its vertex. Proposition 6.2: Let G and H be nite connected graphs. They have a common nite cover in the following cases.

(1) They have the same degree matrix (up to a permutation of rows and columns), that is symmetric.

(2) They are k-regular.

(3) Each of them has exactly one cycle, no loops, and they have isomorphic universal covers.

Proof:

(1) The degree matrix of G and H is the adjacency matrix (counting loops and parallel edges) of a graph M covered by G and H Theorem 6.1 is applicable. Note that M has loops if and only if some values on the diagonal of the adjacency matrix are not null.

(2) The graphs G and H cover the graph with one vertex and k loops. Theorem 6.1 is applicable, which gives the result proved in [START_REF] Angluin | Finite common coverings of pairs of regular graphs[END_REF]. It is a special case of (1).

(3) The graph G is the union of a cycle x 1x 2 -• • •x nx 1 and pairwise disjoint trees T i , each of them having node x i and no node x j , for j 6 = i. Its universal cover U is the union of a biinnite path

• • • -z 0 -z 1 -z 2 -• • • -z n -z n+1 -z n+2 -• • • -z 2n -z 2n+1 -  
and, similarly, of pairwise disjoint trees U i containing nodes z i . The covering homorphism  maps each z p+kn to x p for p ∈ [n] and k ∈ Z and, isomorphically, each tree U p+kn to T p .

Hence, U can be seen, up to isomorphism, as a periodic biinnite sequence of at most n nite trees. From H, we have a similar description. A bininite sequence of the form X Z = Y Z where X has length n and Y has length p is equal to (X p Y ′n ) Z for a circular shift Y ′ of Y . From the sequence X p Y ′n one can build a common cover of G and H.

We can alternatively apply Theorem 6.1. We observe that X and Y ′ are respectively S q and S m for some sequence S, hence, we can dene a loop-free graph M with one cycle covered by G and H if S has length at least 2. If S has length 1, one can dene such a graph M with a loop of weight 2.  By Lemma 4.22, it sufces to prove Theorem 4.10 for nite bipartite graphs, because if two nite graphs G, H have a common universal cover T , then T covers also G × K 2 and H × K 2 that are nite and bipartite. A common nite cover of G × K 2 and H × K 2 is also one of G and H. The proof of [START_REF] Leighton | Finite common coverings of graphs[END_REF] uses this observation. In order to indicate why its proof is difcult, we explain informally why a natural proof generalizing that of Theorem 6.1 fails. Denition 6.3: Quotients of strongly regular labelled trees.

(a) Let T be a tree. It is bipartite with bipartition (N 1 T , N 2 T ) of its nodes. Let  be a labelling of N 1 T  N 2 T  E T . We let ∼ be an equivalence relation on N 1 T  N 2 T  E T such that each equivalence class is included in N 1 T , or in N 2 T or in E T , and two equivalent vertices or edges have the same label. We require that if e and e ′ are equivalent edges, then e : xy, e ′ : x ′y ′ for some x, y, x ′ , y ′ such that x ∼ x ′ and y ∼ y ′  Furthermore, we modify as follows the condition of Denition 4.11:

We do not obtain a proof of Theorem 4.10 because the tree T γ,η constructed from two covering homomorphisms of nite graphs G and H is not necessarily strongly regular. Example 6.5: A tree T γ,η that is not strongly regular.

We let G be the bipartite graph such that V 1 G = a, V 2 G = b, E G = 1, 2, 3, 4, and H similarly be such that V 1 H = c, V 2 H = d, E H = 5, 6, 7, 8 They both have two vertices and four parallel edges. Let  : T → G be a universal covering of G.

We choose adjacent nodes r and s of T such that (r) = a, (s) = b and (e) = 1 where e : r -s. We get a labelled tree T γ . We will enrich its labelling so as to obtain a tree T γ,η for some covering η : T → H.

For this purpose, we replace each node label a of T γ by (a, c), each label b of T γ by (b, d), each edge label 1 by [START_REF] Abello | On the complexity and combinatorics of covering nite complexes[END_REF][START_REF] Bass | Uniform tree lattices[END_REF] and each label 2 by [START_REF] Angluin | Local and global properties in networks of processors[END_REF][START_REF] Berkholz | Tight lower and upper bounds for the complexity of canonical colour renement[END_REF]. Then for each edge in the rooted tree T r -T r s (obtained by deleting T r s from T r ), we replace 3 by (3,7) and 4 by [START_REF] Arnold | Finite transition systems[END_REF][START_REF] Bodlaender | Simulation of large networks on smaller networks[END_REF]; for each edge in the subtree T s -T s r, we replace 3 by (3,8) and 4 by [START_REF] Arnold | Finite transition systems[END_REF][START_REF] Bodlaender | The classication of coverings of processor networks[END_REF].

We get a labelled tree T γ,η related to a universal covering η : T → H.

It is clear that T γ,η is not strongly regular because the edge labels [START_REF] Angluin | Finite common coverings of pairs of regular graphs[END_REF][START_REF] Bodlaender | The classication of coverings of processor networks[END_REF] are present in the part T r -T r s, but not in the other part T s -T s r, and these two parts are innite.  Questions 6.6: Does Theorem 4.10 extend to nite weighted graphs? It does in a somewhat trivial way for graphs whose weights are all ω . Let G and H be two such connected weighted graphs. Let K be their product with V K := V G × V H and (x, y) -(x ′ , y ′ ) in K if and only if xx ′ and yy ′ in G and H respectively. Since ω + ω = ω the two projections π 1 : V K → V G and π 2 : V K = V H are coverings.

The next case to consider would be when weights are 1 or ω.

Conclusion

We have generalized the notions of regular trees studied in [START_REF] Courcelle | Fundamental properties of innite trees[END_REF][START_REF] Courcelle | Recursive applicative program schemes[END_REF], in [START_REF] Arnold | Finite transition systems[END_REF][START_REF] Courcelle | The monadic second-order logic of graphs IX: Machines and their behaviours[END_REF][START_REF] Courcelle | Monadic second-order logic, graph coverings and unfoldings of transition systems[END_REF] and in [START_REF] Angluin | Local and global properties in networks of processors[END_REF][START_REF] Bodlaender | The classication of coverings of processor networks[END_REF][START_REF] Bodlaender | Simulation of large networks on smaller networks[END_REF][START_REF] Norris | Universal covers of graphs: Isomorphism to depth n -1 implies isomorphism to all depths[END_REF] having motivations in program semantics by attaching weights to the arcs or edges of the digraphs or graphs of which we consider complete unfoldings or universal coverings. In particular, innite weights yield trees with nodes of innite degree. Our nite weighted graphs offer effective descriptions and yield decidability results.

The new notion of a strongly regular tree dened as a universal covering of a nite weighted graph is investigated in the companion article [START_REF] Courcelle | Regular and strongly regular innite trees[END_REF].

Examples 2 . 2 :

 22 Weighted relations between weighted sets. (1) Let X consist of a, b, c, d of respective weights 2, 3, 4 and ω and Y consist of u and v of respective weights 5 and ω The mapping κ: a 7 -→ u, b 7 -→ u, c 7 -→ v, d 7 -→ v is a weighted surjection, illustrated in Figure 1. One possible bijection κ ′ satisfying Assertion (1) of Lemma 2.1 is:

Figure 1 .

 1 Figure 1. A weighted surjection, see Example 2.2(1).

  )). If p := d, we can modify accordingly the denition of  ′ . (3) To illustrate Assertion (3), we use X consisting of a, b, c, d of respective weights ω, 4, 2 and ω and Y consisting of u, v, w, x, y of respective weights ω, 4, 3, 5, 1 We can take S to consist of (a, u) and (d, u) of weight ω, (a, v), (c, v), (c, w) and (d, y) of weight 1, (b, v) and (b, w) of weight 2 and (d, x) of weight 5. See Figure 2. This is clearly not the unique way to dene S.

Figure 2 .

 2 Figure 2. The weighted set S of Example 2.2(3).

Denition 3 . 1 :

 31 Weighted digraphs.

Proof: ( 1 )

 1 Figure 3. A digraph G and its quotient G ≈, cf. Example 3.12.

Claim 1 :

 1 The equivalence relation ≈ satises the following property, that we state for an arbitrary equivalence relation R on V H : (E): If xRy then N + H (x) ∼ N + H (y) (mod R). Proof : This follows from Lemma 2.4 and the denitions.  Claim 2: If R is an equivalence relation on V H that satises Property (E), then R ⊆ ≈.

  by Lemma 3.16, and so, (x, y) ∈ R i+1 . Hence, ≈ ⊆ R.The relation R satises Property (E), hence R ⊆ ≈ by Claim 2 in the proof of Theorem 3.14. 

1 )Remark 3 . 21 :

 1321 ' Unf (Hy)  (p -1), we have (x, y) ∈ R p-1 by the claim, hence x ≈ y as was to be proved since R p-1 = ≈ by Proposition 3.18. By the proof of Proposition 3.19, Unf (Hx)  (p -1) ' Unf (Hy)  (p -1) implies Unf (Hx)  i ' Unf (Hy)  i for all i. We might think that this implies Unf (Hx) ' Unf (Hy).

Theorem 3 . 22 :

 322 Given two nite, rooted and weighted digraphs G and H, the following properties are equivalent:1) G and H are unfoldings of a nite rooted and weighted digraph, 2) G and H have isomorphic complete unfoldings, 3) G and H have a common nite unfolding. They are decidable.Proof:Without loss of generality, we assume that G and H are disjoint. 1) =⇒2) If G and H are unfoldings of a nite rooted and weighted digraph M , then the complete unfolding of M is a complete one of both G and H by Theorem 3.5(2). 2) =⇒3) Let  : T → G and η : T → H be complete unfoldings of G and H. If u ∈ N T , then T u ' Unf (G(u)) ' Unf (Hη(u)) by Proposition 3.4(2).

Denition 4 . 1 :

 41 Covering.

  (a) Let G, H be graphs. A covering

Figure 4 .

 4 Figure 4. None of these graphs covers any smaller graph. See Example 4.4.

Example 4 . 4 :

 44 The two graphs of Figure 4 have degree partition (B 1 , B 2 ) where B 1 = a and B 2 consists of the six other vertices. The corresponding matrix is M :=

Theorem 4 . 10 :

 410 Let G, H be nite and connected graphs. The following properties are equivalent.

Denitions 4 . 13 :

 413 Weighted graphs and weight matrices.

(

  a) A weighted graph is a quadruple G = (V, E, Inc, λ) such that (V, E, Inc) is a simple graph (it has no two parallel edges and no two loops at a same vertex) and λ is a weight function: Inc → N +  ω. The two halves of an edge may have different weights.A graph G is made into a weighted graph W (G) as follows: p parallel edges between x and y are fused into a single edge whose two half-edges have weight p; similarly, p loops at x are fused into a single one at x of weight p A simple graph is a weighted graph whose weights are all 1. (b) A nite weighted graph G with vertex set equal to (or indexed by) [p] can be represented by the weight matrix M G : [p] × [p] → N  ω such that M G [x, y] := λ G (e, x) if e : xy. Then the sum of weights of the half-edges is the sum of coefcients of M G . Denition 4.14: Coverings of weighted graphs

Remarks 4 . 15 :

 415 [START_REF] Abello | On the complexity and combinatorics of covering nite complexes[END_REF] If in Denition 4.14, G be a graph, then λ H (e, y) = e ′  e ′ ∈ E G (x), (e ′ ) = e , and, equivalently,  induces a weighted surjection Inc G (x) → (Inc H (y), λ H ) The degree of x in G is the sum of weights of the half-edges in Inc H ((x))

Figure 5 .

 5 Figure 5. See Remark 4.17

For

  an example illustrating this construction, Figure 5 shows the weighted graph H of Example 4.4 with vertices a and b. It shows above an intermediate step H in the construction of G, where  -1 (a) = a ′  and  -1 (b) consists of the six other vertices. The half-edges are solid lines. The matching is shown by dotted lines. The two half-edges that are not matched yield loops in the nal graph shown to the right. Their drawing recalls that they count for one in the degree of their vertices. The graph G covers the same weighted graph H as the two graphs of Figure 4.  As for graphs (Proposition 4.2(1)), we have: Proposition 4.18: Let G, H, K be weighted graphs. If  : G → H and  : H → K are coverings, then so is  •  : G → K. The same holds if G is a graph, or if G and H are graphs.

Example 4 . 23 :H

 423 Weighted graphs, weight matrices and coverings.Every matrixW : [p] × [p] → N  ω such that W [x, y] = 0 implies W [y,x] = 0 is the weight matrix of a nite weighted graph with p vertices. The matrix M := having one edge e : xy, weights λ(e, x) = 3, and λ(e, y) = 2 and a loop at x of weight 1. It is covered by the graph G equal to K 2,3 with an additional edge between the two vertices of degree 3.

Corollary 4 .

 4 26: Let H be a weighted graph with nite weights and vertex set [p]. If it has nite coverings by graphs, then there is a unique p

Denition 5 . 1 :

 51 Universal coverings of weighted graphs.

Figure 6 .

 6 Figure 6. The graph H and the digraph Sym(H) of Example 5.4.

Figure 7 .

 7 Figure 7. The rooted tree Unf (Sym(H) x )  3, see Example 5.4.

  if a node u of Unf (ES(H) x ) is a walk (e 1 , e 2 ,    , e n ) in ES(H) (that starts from x), n > 1, and, for some f ∈ E, either e n-1 = (f + , i), e n = (f -, 1),or e n-1 = (f -, i), e n = (f + , 1), or e n-1 = (f `, i), e n = (f `, 1),then, we remove from Unf (ES(H) x ) the arc from w := (e 1 , e 2 ,    , e n-1 ) to u and the subtree issued from u. (b) We denote by U C(H, x) the rooted tree P r(Unf (ES(H) x )).  If H is a graph, i.e., all weights are 1, then U C(H, x) is as in Denition 4.6. Example 5.6: We continue Example 5.4. Figure 8 shows the rooted tree P r(Unf (Sym(H) x ))  3 = U C(H, x)  3 The rst case of pruning removes the subtree Unf (Sym(H) x )u where u is the head of the arc labelled by e at level 2 in the tree of Figure 7. 

Figure 8 .

 8 Figure 8. The rooted tree U C(H, x)  3 = P r(U nf (Sym(H) x ))  3 See Example 5.6.

Proof: 1 )

 1 By Denition 5.3(c), we have a homomorphism24 ι : ES(H) → H Let x ∈ V H . We have an unfolding homomorphism  : Unf (ES(H) x ) → ES(H) x  It maps the root x of Unf (ES(H) x ) to x. We will prove that the homomorphism ι •  : Unf (ES(H) x ) → Hx induces a covering U nr(U C(H, x)) = U nr(P r(Unf (ES(H) x ))) of H

4 )

 4 As in Theorem 3.5.  Corollary 5.8:(1) If  : T → H is a universal covering and x ∈ N T , then T x ' U C(H, (x)) (2) If x, y ∈ N T and (y) = (x), then T x ' T y .Proof:(1) Follows from the proof of Theorem 5.7(2).(2) If x, y ∈ N T and (y) = (x), then T x ' U C(H, (x)) = U C(H, (x)) ' T y .  As in Denition 4.6, we denote by U C(H) the universal covering of H, that is the isomorphism class of the trees U nr(U C(H, x)) Example 5.9: Figure 9 shows a weighted graph H and, to the right, the digraph ES(H).

  Figure 10 shows the rst two levels of Unf (ES(H) x ). The dotted arcs are eliminated by pruning. 

Figure 9 .

 9 Figure 9. A weighted graph H and the digraph ES(H), see Example 5.9.

Figure 10 .

 10 Figure 10. The tree U nf (ES(H), x)  2, cf. Example 4.11.

Figure 11 .

 11 Figure 11. The top part of the digraph Sym(U C(H, x)), cf. Examples 5.4 and 5.9.

For

  proving the converse, assume U C(H, x)  (p -1) ' U C(H, y)  (p -1). We have also Sym(U C(H, x)  (p-1)) ' Sym(U C(H, y)  (p-1)). The directed walks of length p-1 in ES(H) that start from x are in bijection with the directed paths of length p -1 in Sym(U C(H, x)  (p -1)) that start from x , the root of U C(H, x) It follows that Unf (ES(H) x )  (p -1) ' Unf (ES(H) y )  (p -1) Hence, by Theorem 3.20, we get Unf (ES(H) x ) ' Unf (ES(H) y ) and, by Theorem 5.12, U C(H, x) ' U C(H, y).  Example 5.16: Let us consider the graph H of Example 5.4 and Figures 6,7,8 (Section 5.1). Figure 7 shows Unf (Sym(H) x ))  3, and Figure 8 the result of pruning it. Figure 11 shows the rst three levels of Sym(U C(H, x)) The directed paths of length 3 in the tree Unf (Sym(H) x ) that start from the root x correspond bijectively to the directed walks of length 3 in Sym(U C(H, x)) that start from x In the proof of Theorem 5.15, we use a similar observation for ES(H) where H is weighted. 

Corollary 5 . 25 :

 525 Every node-labelled strongly regular tree is regular.Proof:Immediate from Theorem 5.22 and Proposition 5.21. 

  Inc H and preserves incidences in the obvious way. It maps loops to loops but can map a nonloop edge or arc to a loop. If G and H are rooted, it maps the root of G to that of H. Isomorphism is denoted by ' and the isomorphism class of G by [G] ' 

  and only if v is adjacent to some vertex in [w] ∼ if and only if, by Condition (N), each vertex of [v] ∼ is adjacent to some vertex in [w] ∼ , -the weight λ(e, [v] ∼ ) is the number of edges of T linking v and a vertex in some [w] ∼ such that w is adjacent to v.

	Proof: Condition (N) implies that an edge [v]

∼ -[w] ∼ is dened from an edge vw of T , and that λ(e, [v] ∼ ) is well-dened. The mapping  such that 

It is simply called unfolding in[START_REF] Arnold | Finite transition systems[END_REF][START_REF] Courcelle | The monadic second-order logic of graphs IX: Machines and their behaviours[END_REF][START_REF] Courcelle | Monadic second-order logic, graph coverings and unfoldings of transition systems[END_REF].

Here, we extend the notion of regular tree that arises from the theory of recursive program schemes[START_REF] Courcelle | Fundamental properties of innite trees[END_REF].

In the forthecoming article[START_REF] Courcelle | Regular and strongly regular innite trees[END_REF], we will establish the rst-order denability of regular trees, among all trees, and also of the universal coverings of nite weighted graphs, as described below. These proofs use our extensions of Norris's Theorem.

An edge e : xy and a loop f : zz are equivalent if x ∼ y ∼ z.

Digraph will mean "without weights" and possibly with parallel arcs.

Any two such trees are isomorphic. By thinking of trees up to isomorphism, which is adequate since any two complete unfoldings of a rooted digraph are isomorphic, we can also write the star S ω .

This is a short expression for "the restriction of η to Gu is an unfolding Gu → Hx". Similar shortenings will be used at other places.

Slightly different notions of regular trees are studied in[START_REF] Courcelle | Fundamental properties of innite trees[END_REF][START_REF] Courcelle | The monadic second-order logic of graphs IX: Machines and their behaviours[END_REF][START_REF] Courcelle | Monadic second-order logic, graph coverings and unfoldings of transition systems[END_REF]. However, they have in common the niteness of the set of subtrees T x up to isomorphism.

If G is rooted so that Unf (G) is dened, an equivalent expression of x ≈ y is Unf (G)u ' Unf (G)v where u, v are nodes of Unf (G) such that α(u) = x, α(v) = y and α : Unf (G) → G is the complete unfolding.

In Section 4, weights on half-edges of graphs will be even more important, as they will allow us to describe, as universal coverings of nite weighted graphs, trees of nite degree that are not universal coverings of any nite graph. Furthermore, weights ω will yield trees with nodes of innite degree.

It need not be connected. In order to decide whether Unf (Gx) ' Unf (G ′ y) where G 6 = G ′ , we can use this algorithm by taking for H the union of G and a disjoint copy of G ′ .

It is decreasing for set inclusion. Hence, the equivalence R i+1 renes R i .

The use of boldface letters is intended to recall that U C(H) is only dened up to isomorphism. Most proofs about universal coverings will be done from the concrete trees U nr(U C(H, x)).

By using for instance https://www.dcode.fr/matrix-characteristic-polynomial

See Section 2.2 for homomorphisms from digraphs to graphs.

It maps the root x of U C(H, x) to x.

Note that H ′ is a connected component of H × K 2 dened in Denition 3.21.

Acknowledgements

I thank Yves Métivier for fruitful discussions and the referee for useful comments.

Example 5.11: We continue Example 5.4 illustrated in Figure 6. Figure 7 shows Unf (ES(H) x ). Figure 8 shows P r(Unf (ES(H) x )) = U C(H, x). Figure 11 shows Sym(U C(H, x)) and its upgoing arcs. The deleted arc labelled by e that reaches u(see Figure 7) is restablished towards x. The three arcs outgoing from u and labelled by h, e and g are not. 

The following theorem relates universal coverings to complete unfoldings. We will use it for proving Theorem 5.15 from Theorem 3.20.

Theorem 5.12: Let Hbe a weighted graph. For every two vertices xand y, we have:

If H is nite, this property is decidable.

For the converse, observe that U C(H, x) := P r(Unf (ES(H) x )), hence is dened by using the denition of nodes as walks.

The denition of P r(R) where R := Unf (ES(H) x ) uses a mapping s such that any node u of R that is not the root is mapped by s to one of its sons such that Rs(u) ' Rw where w is the father of u.

Let S := s(u)  u ∈ N R , u 6 = rt R . Then P r(R) is obtained from R by deleting the subtrees Rv for all v ∈ S.

Assume now that R is any rooted tree isomorphic to Unf (ES(H) x ) and that S ′ is any subset of N R such that: each node v in S ′ is at depth at least 2, each node u 6 = rt R has a unique son v in S ′ , and Rv ' Rw where w is the father of u that is itself the father of v.

Then, the labelled rooted trees (Unf (ES(H) x ), S) and (R, S ′ ) are isomorphic 26 . It follows that P r(Unf (ES(H) x )) is isomorphic to the tree obtained from R by deleting the subtrees Rv for all v ∈ S ′ . Hence U C(H, x) can be constructed, u.t.i, from any rooted tree isomorphic to Unf (ES(H) x ) and any appropriate set S ′ , without using the concrete description of the nodes of Unf (ES(H) x ) by walks. It follows that U C(H, x)

The last assertion follows from Theorem 3.14 applied to Sym(H) by using Algorithm 3.18. 

The next proposition denes from a tree a canonical weighted graph of which it is a universal covering.

Proposition 5.13: Let T be a tree and ∼ be an equivalence relation on N T satisfying the following condition:

Common coverings of nite graphs

Our aim is to examine the theorem by Leighton [18] that we stated in Theorem 4.10. Its proof is quite difcult. Alternative no more easier proofs have been given that use tools from combinatorics, topology and group theory [START_REF] Abello | On the complexity and combinatorics of covering nite complexes[END_REF][START_REF] Bass | Uniform tree lattices[END_REF][START_REF] Mohar | A common cover of graphs and 2-cell embeddings[END_REF][START_REF] Neumann | On Leighton's graph covering theorem[END_REF][START_REF] Tucker | Some topological graph theory for topologists: A sampler of covering space construction[END_REF][START_REF] Woodhouse | Revisiting Leighton's theorem with the Haar measure[END_REF]. We will give an easy proof for particular cases, including that of k-regular graphs proved in [START_REF] Angluin | Finite common coverings of pairs of regular graphs[END_REF].

Proof:

We rst assume that G, H and M are loop-free. (They may have parallel edges).

Let  : G → M and  : H → M be coverings. It follows that, if xx ′ is an edge of G, then (x) 6 = (x ′ ), and similarly for . We construct K as follows:

An edge (e, f ) of K links (x, y) and (x ′ , y ′ ) if e : xx ′ and f : yy ′ . We cannot not have (e, f ) linking also (x, y ′ ) and (x ′ , y) because this would mean that (y) = (x) = (x ′ ) contradicting a previous remark.

We dene  : K → G as the rst projection, i.e., (x, y) := x and (e, f ) := e Similarly η : K → H is the second projection. It is clear that  and η are homomorphisms.

We prove that  is surjective. Let x ∈ V G  There is y ∈ V H such that (y) = (x) because  is surjective. Hence (x, y) ∈ V K and (x, y) = x Let e : xx ′ be an edge of G. Then (e) : (x) -(x ′ ) is an edge of M . There is in H an edge f : yy ′ such that (f ) = (e). We have

It remains to prove that  and η are coverings. We prove that for .

Consider (x, y) ∈ V K and its image x in G by . Let e 1 ,    , e p be the edges of G incident with x. Let f 1 ,    , f q be the edges of H incident with y. The edges of M incident with (x) are (e 1 ),    , (e p ) that are pairwise distinct. Those incident with (y) are (f 1 ),    , (f q ), also pairwise distinct. But (x) = (y), hence, q = p, and we can renumber these edges so that (e i ) = (f i ) for each i. The edges of K incident with (x, y) are thus (e i , f i ) for i = 1, , p. Hence  is a covering as wanted. We have

If K is not connected, then each of its connected components is a covering as wanted.

We now consider the case where G, H and M may have loops. It follows from Lemma 4.22 that we have coverings If x and y are equivalent vertices, then, ∼ denes a bijection

We obtain a quotient graph T  ∼ and a covering T → T  ∼ that preserves labels. (b) Let  : T → G be a universal covering of a nite bipartite graph G. We label T as follows. A node x ∈ N T is labelled by (x) and an edge e ∈ E T by (e). The labelled tree T γ is strongly regular. Assume now that η : T → H is a universal covering where H is also a nite and bipartite graph. We dene a labelled tree T γ,η that combines the labels of T γ and of T η : a node x ∈ N T is labelled by ((x), η(x)) and an edge e is labelled by ((e), η(e)).  Letting G, H, , η and T γ,η be as in this denition: Proposition 6.4: If T γ,η is strongly regular, there exists a nite bipartite graph K that is a covering of both G and H.

Proof:

Let ≈ be the equivalence relation on N T γ,η such that x ≈ y if and only if (T γ,η ) x ' (T γ,η ) y . Two equivalent nodes have the same label that is a pair in V G × V H . (However, Example 6.5 below shows that two nodes may have the same label in T γ,η without being equivalent for ≈).

Without assuming that T γ,η is strongly regular, we rst examine the neighbourhood of a node x. Its incident edges have labels (e 1 , f 1 ),    , (e p , f p ) and respective other ends z 1 ,    , z p  In G, the vertex (x) has incident edges e 1 ,    , e p and respective other ends (z 1 ),    , (z p ) In H, the vertex η(x) has incident edges f 1 ,    , f p and respective other ends η(z 1 ),    , η(z p ) If x ′ ≈ x, then, since (T γ,η ) x ' (T γ,η ) x ′ , the edges incident to x ′ have labels (e 1 , f 1 ),    , (e p , f p ) and respective other ends z ′ 1 ,    , z ′ p  Consider an isomorphism : (T γ,η ) x → (T γ,η ) x ′ . Since the edge labels (e 1 , f 1 ),    , (e p , f p ) are pairwise distinct, it maps z i to z ′ i for each i. Hence, it is an isomorphism (T γ,η ) z i → (T γ,η ) z ′ i and z i ≈ z ′ i . It follows that we get a quotient graph K := T γ,η  ≈ that inherits the labels of T

This is well-dened by the above remarks about neighbourhoods in T γ,η .

We claim that K is a covering of both G and H We let κ :

≈ is an edge of K coming from g : xy in T γ,η , we dene κ(m) := (g) Claim: κ : K → G is a covering. Proof : κ is a surjective homomorphism. To prove that it is a covering, we consider a vertex [x] ≈ of K where x is a node in T γ,η . We recapitulate the above observations. The edges of T γ,η incident with x are g 1 ,    , g p with respective ends y 1 ,    , y p and labels (e 1 , f 1 ) ,    , (e p , f p ). The edges of G incident with (x) are e 1 ,    , e p . We get edges [x] ≈ -[y i ] ≈ in K, each with label (e i , f i ) They yield by κ the edges e 1 ,    , e p . Hence, κ is a bijection of E K ([x] ≈ ) to E G (x).  Similarly, we have a covering K → H. Finally, if T γ,η is strongly regular, the equivalence ≈ has nitely many classes and K is nite. 