Benoit Darties

Nicolas Gastineau

Olivier Togni

Almost disjoint spanning trees: relaxing the conditions for completely independent spanning trees

The search of spanning trees with interesting disjunction properties has led to the introduction of edge-disjoint spanning trees, independent spanning trees and more recently completely independent spanning trees. We group together these notions by defining (i, j)-disjoint spanning trees, where i (j, respectively) is the number of vertices (edges, respectively) that are shared by more than one tree. We illustrate how (i, j)-disjoint spanning trees provide some nuances between the existence of disjoint connected dominating sets and completely independent spanning trees. We prove that determining if there exist two (i, j)-disjoint spanning trees in a graph G is NP-complete, for every two positive integers i and j. Moreover we prove that for square of graphs, k-connected interval graphs, complete graphs and several grids, there exist (i, j)-disjoint spanning trees for interesting values of i and j.

In this paper, we introduce (i, j)-disjoint spanning trees: Definition 1.1. Let k ≥ 2 be an integer and T 1 , . . . , T k be spanning trees in a graph G. We let

k} be the set of vertices which are inner vertices in at least two spanning trees among T 1 , . . . , T k , and we let

} be the set of edges which belong to at least two spanning trees among T 1 , . . . , T k . The spanning trees T 1 , . . . , T k are (i, j)-disjoint for two positive integers i and j, if the two following conditions are satisfied:

By * we denote a large enough integer, i.e. an integer larger than max(|E(G)|, |V (G)|), for a graph G. Remark that (0, 0)-disjoint spanning trees are completely independent spanning trees and that ( * , 0)-disjoint spanning trees are edge-disjoint spanning trees. Notice also that there are infinitely many (i, j)-disjoint trees in G, for i ≥ γ c (G) and j ≥ |V (G)| -1, γ c (G) being the minimum size of a connected dominating set in G (one can repeat infinitely the same tree with γ c (G) inner vertices).

Related work

.

For a given tree T and a given pair of vertices (u, v) of T , let P T (u, v) be the set of vertices in the unique path between u and v in T . Remark that T 1 , . . . , T k are internally vertex-disjoint in a graph G if and only if for any pair of vertices

Other works on disjoint spanning trees include independent spanning trees, i.e. focus on finding spanning trees T 1 , . . . , T k rooted at the same vertex r. In independent spanning trees, for any vertex v the paths between r and v in T 1 , . . . , T k are pairwise internally vertex-disjoint, i.e. for each integers i and j, 1 ≤ i < j ≤ k, P Ti (r, v) ∩ P Tj (r, v) = {r, v}. In contrast with the notion of completely

Introduction

The graphs considered are assumed to be connected, since spanning trees are only interesting for connected graphs. Let k ≥ 2 be an integer and T 1 , . . . , T k be spanning trees in a graph G. The spanning trees T 1 , . . . , T k are edge-disjoint if ∪ 1≤ℓ<ℓ ′ ≤k E(T ℓ ) ∩ E(T ℓ ′ ) = ∅. A vertex is said to be an inner vertex in a tree T if it has degree at least 2 in T and a leaf if it has degree 1. We denote by I(T ) the set of inner vertices of tree T . The spanning trees T 1 , . . . , T k are internally vertex-disjoint if I(T 1 ), . . . , I(T k ) are pairwise disjoint. Finally, the spanning trees T 1 , . . . , T k are completely independent spanning trees if they are both pairwise edge-disjoint and internally vertex-disjoint. independent spanning trees, in independent spanning trees only the paths to r are considered. Thus, T 1 , . . . , T k may share common vertices or edges, which is not admissible with completely independent spanning trees. Independent spanning trees have been studied for several classes of graphs which include product graphs [START_REF] Obokata | Independent spanning trees in product graphs and their construction[END_REF], de Bruijn and Kautz digraphs [START_REF] Ge | Disjoint rooted spanning trees with small depths in de Bruijn and Kautz graphs[END_REF][START_REF] Hasunuma | Independent spanning trees with small depths in iterated line digraphs[END_REF], and chordal rings [START_REF] Iwasaki | Independent spanning trees of chordal rings[END_REF]. Related works also include edge-disjoint spanning trees, i.e. spanning trees which are pairwise edge-disjoint only. Edge-disjoint spanning trees have been studied on many classes of graphs, including hypercubes [START_REF] Barden | On edge-disjoint spanning trees in hypercubes[END_REF], Cartesian product of cycles [START_REF] Blough | Multicast in wormhole-switched torus networks using edge-disjoint spanning trees[END_REF] and Cartesian product of two graphs [START_REF] Hung | Constructing edge-disjoint spanning trees in product networks[END_REF]. Some subsets of vertices D 1 , . . . , D k of a graph G are k disjoint connected dominating sets if D 1 , . . . , D k are pairwise disjoint and each subset is a connected dominating set in G. There are some works about disjoint connected dominating sets that can be transcribed in terms of internally vertex-disjoint spanning trees (the disjoint connected dominating sets can be used to provide the inner vertices of internally vertex-disjoint spanning trees). The maximum number of disjoint connected dominating sets in a graph G is the connected domatic number. This parameter is denoted by d c (G) and has been introduced by Hedetniemi and Laskar [START_REF] Hedetniemi | Connected domination in graphs[END_REF] in 1984. An interesting result about connected domatic number concerns planar graphs, for which Hartnell and Rall have proven that, except K 4 (which has connected domatic number 4), their connected domatic number is bounded by 3 [START_REF] Hartnell | Connected Domatic Number in Planar Graphs[END_REF]. The problem of constructing a connected dominating set is often motivated by wireless ad-hoc networks [START_REF] Guba | Approximation Algorithms for Connected Dominating Sets[END_REF][START_REF] Wan | Distributed construction of connected dominating set in wireless ad hoc networks[END_REF] for which connected dominating sets are used to create a virtual backbone in the network.

Motivation and basic facts about disjoint dominating sets

Remark that (0, * )-disjoint spanning trees are internally vertex-disjoint, and consequently, are related to connected dominating sets. Hence, we call (0, * )disjoint spanning trees, trees induced by disjoint connected dominating sets and we give the properties about (0, * )-disjoint spanning trees using, when possible, the concept of disjoint connected dominating sets. Figure 1 illustrates how disjoint connected dominating sets are used to construct (0, * )-disjoint spanning trees. As we observe in the next proposition, trees induced by disjoint connected dominating sets satisfy interesting properties. First, an edge can only belong to at most two trees (Proposition 1.2.i)). Second, the paths between two nonadjacent vertices in trees induced by disjoint connected dominating sets are edge-disjoint (Proposition 1.2.ii)). Moreover, the fact that the paths between two adjacent vertices share a common edge implies that these vertices are inner vertices in different trees (Proposition 1.2.iii)). These properties illustrate the utility of disjoint connected dominating sets to broadcast a message following multiples routes in a network. For a spanning tree, an inner edge is an edge between two inner vertices and a leaf edge is an edge which is not an inner edge.

Proposition 1.2. Let i and j be two integers, 1 ≤ i < j ≤ k. Let G be a dashed lines: edges of T 2 ; dotted lines: edges of T 3 ).

graph of order at least 3, let T 1 , . . . , T k be spanning trees induced by k disjoint connected dominating sets and let u, v ∈ V (G).

i) every edge belongs to at most two trees among T 1 , . . . , T k ;

ii) if u and v are not adjacent, then

P Ti (u, v) ∩ P Tj (u, v) = ∅; iii) if P Ti (u, v) ∩ P Tj (u, v) = ∅ then {u, v} ⊆ I(T i ) and {u, v} ⊆ I(T j ).
Proof. We prove that each of the three properties holds. i) Suppose that uv is an inner edge in a spanning tree. Since the vertices u and v are leaves in any other tree, uv cannot belong to more than one spanning tree. Suppose uv is a leaf edge in at least two trees. The edge uv can belong to at most two trees, the trees for which u and v are inner vertices. ii) Since the paths between u and v in the different trees have length at least 2 and contain no common inner vertices, they share no common edges. iii) By Property ii), u and v are adjacent. Moreover, if u, v ∈ I(T i ), then P Ti (u, v) only contains inner edges of T i , and, as for Property i), each inner edge can not belong to another tree. Since P Ti (u, v) only contains inner edges of T i , P Ti (u, v) ∩ P Tj (u, v) = ∅. The same goes if u, v ∈ I(T j ).

Note that there is a relation between the minimum size of a connected dominating set in a graph G, denoted by γ c (G) and d c (G) (the maximum number of disjoint connected dominating sets) since d c (G) ≤ ⌊|V (G)|/γ c (G)⌋. We also have to mention that Fan, Hong and Liu [START_REF] Fan | Ore's condition for completely independent spanning trees[END_REF] have studied the line graph of cubic graphs of order at least 10 and have proven that there are no two completely independent spanning trees in these cubic graphs. It could be possible, however, that it is not the case for two disjoint dominating sets.

If a graph satisfies d c (G) = k and does not contain k completely independent spanning trees, then there exist an integer j such that G contains k (0, j)-disjoint spanning trees. Hence, the notion of (0, j)-disjoint spanning trees provides some nuances between the existence of disjoint connected dominating sets and completely independent spanning trees.

We say that k connected dominating sets D 1 , . . ., D k are ℓ-rooted connected dominating sets if the set A = ∪ 1≤i<j≤k D i ∩ D j satisfies |A| ≤ ℓ. Remark that we can construct k (ℓ, * )-disjoint spanning trees in a graph that contains k ℓ-rooted connected dominating sets D 1 , . . ., D k by considering that I(T i ) = D i , for every integer i, 1 ≤ i ≤ k. Note also that trees T 1 , . . . , T k induced by 1rooted connected sets, i.e. (1, * )-disjoint spanning trees, are also independent spanning trees rooted at a vertex r ∈ I(T 1 , . . . , T k ). However, if T 1 , . . . , T k are independent spanning trees rooted at r in G, then T 1 , . . . , T k are not always (1, * )-disjoint spanning trees in G. This difference is illustrated by the fact that if for two vertices u, v ∈ V (G) and two spanning trees T i and T j , i = j , we have P Ti (u, r) ∩ P Tj (u, r) = {u, r} and P Ti (v, r) ∩ P Tj (v, r) = {v, r}, then it does not imply that P Ti (u, v) ∩ P Tj (u, v) = {u, v, r}.

Notation and Organization

We denote by δ(G) the minimum degree of G, i.e., δ(G) = min{N (u)| u ∈ V (G)}. We denote by d G (u, v) the usual distance between two vertices u and v in a graph G. The graph Ge is the graph obtained from G by removing an edge e from E(G) and G -A, for A ⊆ V (G), is the graph obtained from G by removing the vertices from A and their incident edges. For A ⊆ V (G), we denote by

G[A], the graph G-(V (G)\A). We say that a graph G is k-connected if |V (G)| ≥ k + 1 and if for any set of vertices A ⊆ V (G), with |A| ≤ k -1, G-A is connected. By K n , P n
and C n , we denote the complete graph, path and cycle, respectively, of order n. Let n 1 and n 2 be positive integers. By G(n 1 , n 2 ) we denote the square grid with n 1 rows and n 2 columns. The graph G(n 1 , n 2 ) can be also defined as the Cartesian product of two paths P n1 and P n2 . The cylinder, denoted by C(n 1 , n 2 ), is the Cartesian product of one cycle C n1 and one path P n2 .

This article is organized as follows. Section 2 presents alternative characterizations of (i, j)-disjoint spanning trees. Section 3 is about the computational complexity of the following decision problem: is it true that a graph G contains two (i, j)-disjoint spanning trees (with input the graph G). Section 4 deals with k-connectivity and the conditions of Dirac and Ore for (i, j)-disjoint spanning trees. Section 5 is about the required number of edges and distribution of inner vertices in (i, j)-disjoint spanning trees. Section 6 presents some (i, j)-disjoint spanning trees in square of graphs, k-connected interval graphs, complete graphs, and square grids and cylinders.

Characterizations in terms of partitions and dominating sets

We begin this section by proving the following proposition.

Proposition 2.1. Let G be a connected graph of order at least 3 and let T 1 , . . . , T k be (i, j)-disjoint spanning trees in G. For every integer ℓ, 1 ≤ ℓ ≤ k, every vertex u ∈ V (G) satisfies the two following properties: i) if u / ∈ I(T ℓ ), then u has a neighbor in I(T ℓ );

Figure 2: An 1-CIST partition (on the left) and an 1-rooted partition (on the right) of two graphs (circles: V 1 ; triangles: V 2 ; square: A).

ii) if G has diameter at least 3, then u has a neighbor in I(T ℓ ).

Proof. Suppose there exist an integer ℓ, 1 ≤ ℓ ≤ k, and a vertex u which has no neighbor in I(T ℓ ). i) If u / ∈ I(T ℓ ), then G = T ℓ = P 2 which contradicts the hypothesis that G has order at least 3. ii) Since property i) holds, we suppose that u ∈ I(T ℓ ). Remark that since G has diameter at least 3, a spanning tree of G has also diameter at least 3. Moreover, if u is only adjacent to leaf vertices then it implies that T ℓ is a star which contradicts the fact that T ℓ has diameter at least 3.

Let V 1 and V 2 be two subsets of vertices of a graph G. By B(V 1 , V 2 ) we denote the bipartite graph with vertex set V 1 ∪V 2 and edge set {uv ∈ E(G)| u ∈ V 1 , v ∈ V 2 }.
In the two following subsections we give alternative characterizations of (0, ℓ)-disjoint spanning trees and ℓ-rooted connected dominating sets. These characterizations are expressed in terms of partition in sets of vertices fulfilling some properties.

(0, ℓ)-disjoint spanning trees

In this subsection, we introduce a definition which is inspired by the definition of CIST-partition introduced by Araki [START_REF] Araki | Dirac's condition for completely independent spanning trees[END_REF].

Definition 2.2. An ℓ-CIST-partition of a graph G into k sets is a partition of V (G) into k sets of vertices V 1 , . . . , V k such that: i) G[V i ] is connected, for each integer i, 1 ≤ i ≤ k; ii) B(V i , V j ) contains no isolated vertex, for every two integers i, j, 1 ≤ i < j ≤ k; iii) 1≤i<j≤k c i,j ≤ ℓ, where c i,j is the number of connected component which are trees in B(V i , V j ), 1 ≤ i < j ≤ k.
Figure 2 illustrates an 1-CIST partition on a specific graph. In a similar way than Araki [START_REF] Araki | Dirac's condition for completely independent spanning trees[END_REF], we prove that the notions of ℓ-CIST partition and (0, ℓ)-disjoint spanning trees are equivalent.

Theorem 1. Let G be a graph. There exist k (0, ℓ)-disjoint spanning trees T 1 , . . . , T k in G if and only if G has an ℓ-CIST-partition into k sets.

Proof. Suppose G has an ℓ-CIST-partition into k sets V 1 ,. . . ,V k . We are going to construct (0, ℓ)-disjoint spanning trees T 1 , . . . , T k . We begin by setting I(T i ) = V i for each integer i, 1 ≤ i ≤ k. For each integer i, 1 ≤ i ≤ k, we suppose that E(T i ) is empty and we progressively add edges to T i in order to obtain spanning trees of G at the end of the proof. Since G[V i ] is connected for each integer i, 1 ≤ i ≤ k, it is possible to add edges to T i in order to have a spanning tree with inner vertices from V i , for each integer i.

Let i and j be two integers, 1 ≤ i < j ≤ k, and let D i,j be a connected component of B(V i , V j ). We add edges in order to build a spanning tree restricted to V i ∪ V (D i,j ) and another spanning tree restricted to V j ∪ V (D i,j ) by considering two cases. Let u be a vertex of D i,j ∩ V i . First, if D i,j is a tree, then we add an edge e of D i,j incident with u to both T i and T j . Thus, the edge e will be common to T i and

T j . Let D d i,j (u) = {v ∈ V (D i,j )| d Di,j (u, v) = d}. We add to T i the edges of the set {vv ′ ∈ E(D i,j )| v ∈ D d i,j (u), v ′ ∈ D d+1 i,j (u), d is even} and to T j the edges of the set {vv ′ ∈ E(D i,j )| v ∈ D d i,j (u), v ′ ∈ D d+1 i,j (u), d is odd}. Second, if D i,j
is not a tree, then we suppose that u is in a cycle of D i,j . Let e be an edge of this cycle incident with u and let T i,j be a spanning tree of D i,je. We define

B d i,j (u) as follows: {v ∈ V (D i,j )| d Ti,j (u, v) = d}. We add to T i the edges of the set {vv ′ ∈ E(T i,j )| v ∈ B d i,j (u), v ′ ∈ B d+1 i,j (u), d is even} and to T j the edges of the set {vv ′ ∈ E(T i,j )| v ∈ B d i,j (u), v ′ ∈ B d+1 i,j (u), d is odd} ∪ {e}.
We repeat this process for every connected component of B(V i , V j ) and every two integers i and j, 1 ≤ i < j ≤ k. Since there is only one common edge between T i and T j for each connected component that is a tree and since 1≤i<j≤k c i,j ≤ ℓ, the set E(T 1 , . . . , T k ) contains at most ℓ edges. Therefore, we obtain, by Property ii), k (0, ℓ)-disjoint spanning trees.

Let us prove the converse of the previous implication. Suppose there exist k (0, ℓ)-disjoint spanning trees T 1 , . . . , T k in G. The set I(T i ), 1 ≤ i ≤ k, induces a connected subgraph in G. We begin by setting V i = I(T i ), for each integer i, 1 ≤ i ≤ k. If some vertices are inner vertices in no trees, we can add them to any set among V 1 , . . . , V k . Thus, Property i) follows. Let i and j be two integers, 1 ≤ i < j ≤ k. Suppose there exists one isolated vertex u in B(V i , V j ). Without loss of generality, suppose u ∈ V i . By Proposition 2.1.i), we obtain a contradiction since u / ∈ I(T j ) and u has no neighbor in I(T j ). Thus, Property ii) follows. Now suppose 1≤i<j≤k c i,j > ℓ. Let D i,j be a connected component which is a tree in B(V i , V j ) for some integers i and j and suppose that D i,j contains no edge from E(T 1 , . . . , T k ).

Since D i,j has |V (D i,j )| -1 edges, it is impossible that every vertex of V (D i,j ) ∩ V i is adjacent to a vertex of V (D i,j ) ∩ V j in T j and that every vertex of V (D i,j ) ∩ V j is adjacent to a vertex of V (D i,j ) ∩ V i in T i , since it would require |V (D i,j )| edges.
Thus, for every two integers i and j and every connected component

D i,j of B(V i , V j ), if D i,j is a tree then V (D i,j ) ∩ E(T 1 , . . . , T k ) = ∅ and we obtain a contradiction since 1≤i<j≤k c i,j > ℓ implies |E(T 1 , . . . , T k )| > ℓ. Consequently, Property iii) follows.

(ℓ, * )-disjoint spanning trees

For a graph G and a subset of vertices

A ⊆ V (G), let N (A) = {u ∈ V (G) \ A| uv ∈ E(G), v ∈ A}.
In a similar way than Zelinka [START_REF] Zelinka | Connected domatic Number of a graph[END_REF], we prove that the notion of ℓ-rooted connected dominating sets is equivalent to a notion of partition. Proof. Suppose G has an ℓ-rooted

Definition 2.3. An ℓ-rooted partition of G into k + 1 sets is a partition of V (G) into k + 1 sets of vertices V 1 , . . . , V k , A such that: i) |A| ≤ ℓ; ii) G[V i ∪ A] is connected, for each integer i, 1 ≤ i ≤ k; iii) B(V i , V j ) -N (A) contains no isolated vertex, for every two integers i and j, 1 ≤ i < j ≤ k.
partition into k + 1 sets V 1 , . . . , V k , A. We begin by setting D i = V i ∪ A for each integer i, 1 ≤ i ≤ k. Since V 1 , . . . , V k , A is a partition, we have | ∪ 1≤i<j≤k D i ∩ D j | ≤ ℓ.
Moreover, by Property ii), the subgraphs induced by the sets D 1 ,. . . , D k are all connected. It remains to prove that D i is a dominating set, for each integer i, 1 ≤ i ≤ k. Since the vertices of N (A) are already dominated by a vertex of A ⊆ D i , for each integer i, Property iii) implies that every vertex of V (G) \ (V i ∪ N (A)) has a neighbor in V i , for each integer i. Suppose there exist k ℓ-rooted connected dominating sets D 1 , . . . , D k in G. We begin by setting A = ∪ 1≤i<j≤k D i ∩ D j . Afterward, we set V i = D i \ A, for each integer i, 1 ≤ i ≤ k. By definition, Property i) and Property ii) are satisfied by V 1 , . . . , V k , A. It remains to prove Property iii). By contradiction, suppose that a vertex u ∈ V i has no neighbor in V j ∪A, for some integers i and j. This fact implies that D j is not a dominating set and Property iii) follows.

In the following definition we introduce the construction of a graph denoted by G(k, A). Definition 2.4. Let G be a graph, k be an integer and A = {u 1 , . . . , u ℓ } ⊆ V (G) be a subset of vertices. We denote by G(k, A) the graph obtained by replacing one by one each vertex u i , for 1 ≤ i ≤ ℓ, by a complete graph of order k, and by adding edges between each vertex of this clique and every vertex of N (u i ).

We finish by proving that determining if a graph G contains k ℓ-rooted connected dominating sets is equivalent to determine if the graph G(k, A) has ℓ disjoint connected dominating sets, for some subset of vertices A ⊆ V (G). In contrast with the two previous propositions, this alternative characterization is expressed in terms of disjoint dominating sets. Proof. Let G be a graph. Suppose there exist k ℓ-rooted connected dominating sets D 1 , . . . , D k in G. We begin by setting

A = ∪ 1≤i<j≤k D i ∩D j . Let K i k denote the clique from G(k, A) which replaces the vertex u i in G(k, A), for 1 ≤ i ≤ ℓ. We can construct k disjoint connected dominating sets D ′ 1 , . . . , D ′ k in G(k, A) as follows: for each integer j, 1 ≤ j ≤ k, D ′ j contains the vertices from D j \ A and one different vertex by clique K i k , for each integer i, 1 ≤ i ≤ ℓ. Suppose there exist a subset of vertices A ⊆ V (G) such that |A| ≤ ℓ and d c (G(k, A)) ≥ k. Let D ′ 1 , . . . , D ′ k be disjoint connected dominating sets in G(k, A). We can construct k ℓ-rooted connected dominating sets D 1 , . . . , D k in G as follows: for each integer j, 1 ≤ j ≤ k, D j contains the vertices from D ′ j \ (K 1 k ∪ . . . ∪ K ℓ k ) ∪ {u 1 , . . . , u ℓ }.
3 An NP-complete problem for every integers i and j

We define the following decision problem:

k-(i, j)-DSP Instance : A graph G. Question: Does there exist k (i, j)-disjoint spanning trees in G ?

Theorem 3. Let i and j be non negative integers. The problem 2-(i, j)-DSP is an NP-complete problem for every pair of integer (i, j).

Proof. Hasunuma [START_REF] Hasunuma | Completely independent spanning trees in maximal planar graphs[END_REF] has proved that the following problem is NP-complete:

2-(u, v)-CIST

Instance : A graph G and two vertices u and v of V (G). Question: Does there exist two completely independent spanning trees T 1 and T 2 in G with u ∈ I(T 1 ) and v ∈ I(T 2 ) ?

Initially, the NP-complete problem considered by Hasunuma [START_REF] Hasunuma | Completely independent spanning trees in maximal planar graphs[END_REF] consists in determining if there exist two completely independent spanning trees in a graph G. However, by analyzing Hasunuma's reduction we can also obtain that the problem 2-(u, v)-CIST is NP-complete by using the same reduction (it suffices to consider that u is v B and that v is v R in Hasunuma's reduction). Also, it is trivial to prove that the problem 2-(i, j)-DST is in NP since the description of two spanning trees in a graph G (when dst i,j (G) ≥ 2) ensures the existence of these two (i, j)-disjoint spanning trees. We use a reduction from 2-(u, v)-CIST.

We introduce the three following operations that will be useful to describe our reduction: i) H-add is an operation on a graph with two prescribed vertices w 1 and w 2 that consists in adding the graph H from Figure 3 and identifying w 1 with p 1 and w 2 with p 2 ;

p 2 p 1 p ′ 2 p ′ 1 p 2 p 1 y y ′ p ′ 2 p ′ 1 p 2 p 1 x
ii) H ′ -add is an operation on a graph with two prescribed vertices w 1 and w 2 that consists in adding the graph H ′ from Figure 3 and identifying w 1 with p 1 and w 2 with p 2 ;

ii) H + -add is an operation on a graph with two prescribed vertices w 1 and w 2 that consists in adding the graph H + from Figure 3 and identifying w 1 with p 1 and w 2 with p 2 ;

Let G be a graph and let u and v be two vertices of V (G). We construct a graph G ′ from G as follows. Let ℓ ≥ 1 be a positive integer. We begin by constructing two graphs H ℓ and H ′ ℓ by induction. The graph H 1 is the graph H and the graph H ′ 1 is the graph H ′ . The graph H ℓ+1 is obtained from H ℓ by doing an H-add on the two vertices of degree 3 in H ℓ (denoted by p ′ 1 and p ′ 2 in the left part of Figure 3, for ℓ = 1). The graph H ′ ℓ+1 is obtained from H ′ ℓ by doing an H ′ -add on the two vertices of degree 3 (also denoted by p ′ 1 and p ′ 2 in the middle part of Figure 3, for ℓ = 1). In H ℓ and H ′ ℓ , we denote by p ′ 1 and p ′ 2 the two remaining vertices of degree 3. Finally, the graph H i,j is obtained by taking H i and H ′ j , identifying p ′ 1 in H i with a vertex of degree one in H ′ j and p ′ 2 in H i with the other vertex of degree one in H ′ j and doing a H + -add on the two vertices of degree 3 which are labeled by p ′ 1 and p ′ 2 in H ′ j . The graph G ′ is obtained by taking a copy of G, adding H i,j , identifying the vertex u with a vertex of degree one in H i,j and identifying the vertex v with the other vertex of degree one in H i,j .

Suppose there exist two completely independent spanning trees T 1 and T 2 in G with u ∈ I(T 1 ) and v ∈ I(T 2 ). We can construct two (i, j)-disjoint spanning trees in G ′ by reproducing the trees T 1 and T 2 in the graph G ′ restricted to G and by using the patterns described in Figure 4 in order to extend the spanning trees to H i,j . Suppose there exist two (i, j)-disjoint spanning trees T 1 and T 2 in G ′ . Note that there are i articulation vertices in the graph G ′ restricted to H i,j . These i articulation vertices should be inner vertices in both T 1 and T 2 . Thus, the trees T 1 and T 2 restricted to G are internally vertex-disjoint. By Proposition 2.1, the vertex x (obtained by H + -add in H i,j and illustrated in Figure 3) should be adjacent to an inner vertex of T 1 and to an inner vertex of T 2 . Thus in order that T 1 and T 2 be connected, there must be a path from x to u in T 1 and a path from x to v in T 2 (we can exchange T 1 and T 2 if necessary). Note that the vertices y and y ′ from a copy of H ′ (illustrated in Figure 3) cannot be both inner vertices of the same tree since it would be impossible to have a path from x to u in T 1 and another path from x to v in T 2 . Thus, in order that y and y ′ belong to both T 1 and T 2 , the edge yy ′ should belong to both T 1 and T 2 (since we already have i articulation vertices). Moreover, since there are j copies of H ′ in the graph H i,j , the trees T 1 and T 2 restricted to G are both internally vertex-disjoint and edge-disjoint.

4 Sufficient conditions to have (i, j)-disjoint spanning trees

k-connectivity

We begin this section by proving classical properties about cut sets. Proof. Let A ⊆ V (G) be a subset of vertices such that |A| < k and G -A is not connected. Remark that I(T ℓ ) ∩ A should not be empty, for every integer ℓ, 1 ≤ ℓ ≤ k, since it would imply that T ℓ is not connected. Since |A| < k, a vertex of A should be in I(T 1 , . . . T k ). The same property holds for B.

Proposition 4.2. Let G be a graph and let T 1 , . . . , T k be (i, j)-disjoint spanning trees in G. Let a be the number of articulation vertices which do not belong to bridges in G and let b be the number of bridges in G. We have i ≥ a + 2b and j ≥ b.

Proof. Since an articulation vertex belongs to every spanning tree of G, we have i ≥ a. The same goes for the bridges and their extremities.

Since the presence of a k-cut in a graph G implies that there do not exist k+1 disjoint connected dominating set, it is natural to ask whether a k-connected graph, for k sufficiently large, contains at least two disjoint connected dominating sets [START_REF] Hedetniemi | Connected domination in graphs[END_REF]. In the paper in which completely independent spanning trees have been introduced [START_REF] Hasunuma | Completely independent spanning trees in the underlying graph of line graph[END_REF], the same question has been asked for two completely independent spanning trees.

Using the construction from Kriesell [START_REF] Kriesell | Edge-disjoint trees containing some given vertices in a graph[END_REF] or Péterfalvi [START_REF] Péterfalvi | Two counterexamples on completely independent spanning trees[END_REF], we can obtain a family of k-connected graphs that do not contain two completely independent spanning trees. We recall the construction of the family of graphs considered by Kriesell [START_REF] Kriesell | Edge-disjoint trees containing some given vertices in a graph[END_REF].

| i ∈ A, u A ∈ V (G k,ℓ ), 1 ≤ i ≤ ℓ}.
The graph G k,ℓ corresponds to the incidence graph of the complete k-uniform hypergraph with ℓ vertices.

Note that the graph G k,ℓ is k-connected and bipartite. Using a similar proof than that of Kriesell, we obtain the following theorem which shows that there exist k-connected graphs which do not contain two (i, j)-disjoint spanning trees, for every three positive integers k ≥ 2, i and j. Theorem 4. Let i, j and k ≥ 2 be integers. For any ℓ ≥ 2k + i -1, the graph G k,ℓ does not contain two (i, j)-disjoint spanning trees.

Proof. Suppose there exist two (i, j)-disjoint spanning trees T 1 and T 2 in G k,ℓ . Let H 1 and H 2 be the two subsets of vertices forming a bipartition of G k,ℓ , with

H 1 = {1, . . . , ℓ} and H 2 = {u A | A ⊆ {1, . . . ℓ}, |A| = k}. Let B = I(T 1 , T 2 )∩H 1 .
Note that, by definition of (i, j)-disjoint spanning trees, |B| ≤ i. We consider a set A 0 ⊂ H 1 \ B, |A 0 | = k. By Proposition 2.1, at least one inner vertex of T 1 is adjacent to u A0 . This inner vertex of T 1 is denoted by v 0 . Inductively, since |H 1 | = ℓ ≥ 2k + i -1, for 1 ≤ q ≤ k -1 , we can create a set A q ⊆ H 1 \ (B ∪ {u 0 , . . . , u q-1 }) with |A q | = k and obtain that there exists a vertex v q ∈ A q ∩ I(T 1 ) adjacent to u Aq . The set D = {v 0 , . . . , v k-1 } ⊆ H 1 is such that |D| = k and D ⊆ I(T 1 ). Hence, we have a contradiction with Proposition 2.1.ii), since u D has no neighbor which is a inner vertex of T 2 and G k,ℓ has diameter greater than 2 when ℓ > k.

Dirac's and Ore's conditions

We begin this subsection by proving that there are at least two disjoint dominating sets in some particular graphs. Proof. These disjoint connected dominating sets are illustrated in Figure 5. ∈ E(G)} ≥ n -1, that does not contain two disjoint connected dominating sets. Such graph can be constructed by taking two complete graphs K ⌊(n+1)/2⌋ and K ⌈(n+1)/2⌉ , for n a positive integer, and by identifying a vertex of the first clique with a vertex of the second clique. This fact implies that the bounds in the previous theorems are tight. It could be possible to improve the recent results about Dirac's condition [START_REF] Chang | A note on the degree condition of completely independent spanning trees[END_REF][START_REF] Hasunuma | Minimum degree conditions and optimal graphs for completely independent spanning trees[END_REF][START_REF] Hong | Degree condition for completely independent spanning trees[END_REF] by only considering disjoint connected dominating sets.

5 Number of inner vertices and edges in (i, j)disjoint spanning trees

Required number of edges

We begin this section by giving necessary conditions on the number of edges of a graph G in order to have k (i, j)-disjoint spanning trees.

Proposition 5.1. Let G be a graph of order n and let T 1 , . . . , T k be (i, j)-disjoint spanning trees in G. We have

|E(G)| ≥ k(n -1) -j(k -1).
Proof. Suppose G contains at least k (i, j)-disjoint spanning trees. Since every spanning tree contains n -1 edges and since an edge in E(T 1 , . . . T k ) can be in at most k trees, we obtain that G contains at least k(n -1)j(k -1) edges. Note that the grid G(2, n) satisfies the equality for k = 2 and j = n. This last proposition can be improved for i = 0 [START_REF] Hartnell | Connected Domatic Number in Planar Graphs[END_REF] since, by Proposition 1.2.i), an edge in E(T 1 , . . . T k ) can be in at most two trees.

Corollary 5.2. Let G be a graph of order n and let T 1 , . . . , T k be (0, j)-disjoint spanning trees in G. We have

|E(G)| ≥ k(n -1) -j.
Moreover, for an arbitrary large j, the following bound is known.

Proposition 5.3. [10] A graph G of order n such that d c (G) ≥ k has at least n(k + 1)/2 -k edges. This bound is sharp since d c (K k,k ) = k.

Distribution of the inner vertices

The following observation illustrates the existence of an (i, j)-disjoint spanning tree with possibly less inner vertices than the others. Observation 5.4. Let G be a graph of order n and let T 1 , . . . , T k be (i, j)disjoint spanning trees in G. There exists a tree T among T 1 , . . . , T k satisfying |I(T )| ≤ ⌊(ni)/k⌋ + i.

Two sets of vertices

V 1 and V 2 are balanced if ||V 1 | -|V 2 || ≤ 1.
We begin by proving that there exists a graph G satisfying d c (G) ≥ 2 but in which no two disjoint connected dominating sets are balanced. Let P * n be the graph constructed by taking one copy of P n , by adding a new vertex u and by adding the edges between u and the vertices of P n . Figure 6 Note that the graph P * n does not contain two completely independent spanning trees. Thus, it could be true that every graph containing two completely independent spanning trees contains two completely independent spanning trees T 1 and T 2 such that ||I(T 1 )| -|I(T 2 )|| ≤ 1. However, the following proposition illustrates that it is not the case. Let P + n be the graph obtained by taking one copy of P * n , by adding a new vertex v and by adding the edge uv and the edges between v and the extremities of P n , u being the vertex of maximal degree in P * n , P n being the induced path of n vertices in P * n obtained by removing u. Figure 6 illustrates the graph P + n for n = 6. Proposition 5.6. Let n ≥ 3. For any two completely independent spanning trees T 1 and T 2 in

P + n , ||I(T 1 )| -|I(T 2 )|| ≥ n -2.
Proof. First, observe that there exist two completely independent spanning trees in P + n since {u, v} and V (P + n ) \ {u, v} is a 0-CIST-partition. Now, suppose there exist two completely independent spanning trees T 1 and T 2 and suppose without loss of generality that u / ∈ I(T 1 ). Since the graph induced by the vertices of I(T 1 ) should be connected, it should contain consecutive vertices of P n . Moreover, I(T 1 ) should be dominating set. Since either {u} and the subsets of V (P + n ) \ {u} or {u, v} and the proper subsets of V (P + n ) \ {u, v} do not form a 0-CIST partition, we have I(T 1 ) = V (P + n )\{u, v} and I(T 2 ) = {u, v}. Therefore, we have

||I(T 1 )| -|I(T 2 )|| ≥ n -2.
Even if there exist graphs only containing two non-balanced disjoint connected dominating sets, it could be interesting to find classes of graphs for which there always exist two disjoint connected dominating sets which are balanced. For example, the class of graphs with minimum degree at least |V (G)|/2, is such a class [START_REF] Hong | Degree condition for completely independent spanning trees[END_REF].

6 (i, j)-disjoint spanning trees in some simple classes of graphs

Square of graphs

The square of a graph G, denoted by G 2 , is the graph obtained from G by adding edges between every two vertices u and v of G with d G (u, v) = 2. Araki [START_REF] Araki | Dirac's condition for completely independent spanning trees[END_REF] has studied the square of graphs and has proven that there exists a tree T such that there are no two completely independent spanning trees in T 2 and that in the square of every 2-connected graph, there are two completely independent spanning trees. Moreover, the family of trees such there are no two completely independent spanning trees in T 2 has been determined. We begin this section by proving that there exist two (0, 1)-disjoint spanning trees in the square of every graph.

Proposition 6.1. Let G be graph. There exist two (0, 1)-disjoint spanning trees in G 2 .

Proof. Let T be a spanning tree of

G let V 1 and V 2 be a bipartition of T . The sets V 1 and V 2 form an 1-CIST-partition of G 2 since both G[V 1 ] and G[V 2 ] are connected in G 2 and since B(V 1 , V 2
) is a connected graph (which can be a tree in the case G is a tree). Thus, by Theorem 1, there exist two (0, 1)-disjoint spanning trees in G 2 .

We finish the section by determining which square of graph contains two completely independent spanning trees (the case of trees has already been treated [START_REF] Araki | Dirac's condition for completely independent spanning trees[END_REF]). Proposition 6.2. Let G be a connected graph which is not a tree. There exist two completely independent spanning trees in G 2 .

Proof. Since G is not a tree, there exists an induced cycle C in G. Let u be a vertex of C which has a neighbor v not belonging to C. If such vertex does not exist, then G is cycle and G 2 contains two completely independent spanning trees [START_REF] Araki | Dirac's condition for completely independent spanning trees[END_REF]. Let uw be an edge of C, let T be a spanning tree of Guw and let V 1 and V 2 be a bipartition of T . Remark that both G[V 1 ] and G[V 2 ] are connected and that every edge of T belongs to B(V 1 , V 2 ). Our goal is to prove that there is one more edge in

B(V 1 , V 2 ), i.e, that B(V 1 , V 2 ) is connected and is not a tree. First, if C is of even length, then u ∈ V 1 and w ∈ V 2 (or u ∈ V 2 and w ∈ V 1 , by symmetry) and uw ∈ E(B(V 1 , V 2 )) \ E(T ). Second if C is of odd length, then u ∈ V 1 , w ∈ V 1 and v ∈ V 2 (or v ∈ V 1 , u ∈ V 2 and w ∈ V 2 , by symmetry) and vw ∈ E(B(V 1 , V 2 )
) \ E(T ). Thus, by Theorem 1, there exist two completely independent spanning trees in G 2 .

Note that the square of a star (a tree of diameter at most 2) is a clique and can contain an arbitrary large number of completely independent spanning trees (this number depends on the degree of the central vertex). Thus, it could be interesting to determine which square of graph contains k completely independent spanning trees for k > 2.

k-connected interval graph

We begin by recalling the definition of a path-decomposition of a graph G. Definition 6.3. Let G be a graph. A sequence of subsets X 1 , . . . , X ℓ of vertices of G is a path-decomposition of G if the two following properties are satisfied: i) for each edge e of G, there exists an integer i such that both extremities of e belong to the subset X i ;

ii) for every three integers

1 ≤ i ≤ j ≤ k ≤ ℓ, X i ∩ X k ⊆ X j .
An interval graph is the intersection graph of a family of intervals of the real line. We recall that an interval graph has a path-decomposition X 1 , . . . , X ℓ for which each X i , 1 ≤ i ≤ ℓ, forms a maximal clique in G. We also recall that for a k-connected interval graph G with path-decomposition X 1 , . . . , X ℓ , we have |X i ∩ X i+1 | ≥ k, for every integer i, 1 ≤ i < ℓ (otherwise X i ∩ X i+1 would be a cut set of order less than k). The following property is true for k-connected interval graphs. Proof. Let G be a k-connected interval graph. Let X 1 , . . . , X ℓ be a pathdecomposition of G, for which every X i forms a maximal clique. If ℓ = 1, then G is a k-connected complete graph, i.e., G = K n for n ≥ k. Thus G satisfies d c (G) = n ≥ k. Hence, suppose ℓ ≥ 2. Our goal is to construct disjoint connected dominating sets D 1 , . . . , D k by setting

D i = ∪ 1≤j≤ℓ-1 {x j i }, for 1 ≤ i ≤ k.
By hypothesis, |X 1 ∩X 2 | ≥ k, and there exist

k different vertices x 1 1 , . . . , x 1 k ∈ X 1 ∩ X 2 forming k disjoint connected dominating sets on the graph G[X 1 ∪ X 2 ].
We set D i = {x 1 i }, for every integer i, 1 ≤ i ≤ k. Suppose ℓ > n and that, by induction, that we have already determined x 1 i , . . . , x n-1 i , for every integer i, 1 ≤ i ≤ k and that D 1 , . . . , D k are disjoint connected dominating sets on the graph G[X 1 ∪ . . . ∪ X n ], for D i = ∪ 1≤j≤n-1 {x j i }. Now our goal is to construct disjoint connected dominating sets on the graph G[X 1 ∪ . . . ∪ X n+1 ].

Let i be an integer, The previous theorem can not be generalized to chordal graphs since there exist k-connected chordal graphs, for k ≥ 2, which do not contain two disjoint connected dominating sets [START_REF] Péterfalvi | Two counterexamples on completely independent spanning trees[END_REF].

1 ≤ i ≤ k. If X n ∩ X n+1 ∩ {x j i } = ∅,

Complete graphs

By dst i,j (G) we denote the maximum number of (i, j)-disjoint spanning trees in G. Remark that there are n disjoint connected dominating sets in K n and that there are ⌊n/2⌋ completely independent spanning trees in K n [START_REF] Matsushita | Completely independent spanning trees in (partial) k-trees[END_REF].

We give the following intermediate result about (0, ℓ)-disjoint spanning trees.

Proposition 6.4. Let n be an integer. We have dst 0,ℓ (K n ) = ⌊n/2⌋+min(⌊ℓ/(n-1) + 1 odd (n)/2⌋, ⌈n/2⌉), where 1 odd (n) = 1 if n is odd and 0 otherwise.

Proof. First, suppose n is even. Let i = ⌊ℓ/(n -1)⌋. We begin by proving that dst 0,ℓ (K n ) < n/2 + i + 1 for 0 ≤ i < n/2. Suppose that there are n/2 + i + 1 (0, ℓ)-disjoint spanning trees. By Corollary 5.2, we have

|E(K n )| ≥ (n/2 + i + 1)(n -1) -ℓ. Observe that (n/2 + i + 1)(n -1) -ℓ = n(n + 1)/2 + i(n -1) -1 -ℓ. Since |E(K n )| = n(n -1)/2, we have ℓ ≥ i(n -1) + n -1 = (i + 1)(n -1),
contradicting the definition of i. We are going to prove that we can construct n/2 + i (0, ℓ)-disjoint spanning trees in K n , for 1 ≤ i ≤ n/2. We construct two kinds of spanning trees. First, we construct 2i spanning trees T 1 , . . . , T 2i which are spanning stars. Second, we construct n/2i spanning trees in K n each tree with two inner vertices, as in [START_REF] Matsushita | Completely independent spanning trees in (partial) k-trees[END_REF] (with disjoint inner vertices). The left part of Figure 7 illustrates this construction for K 6 . There are 2i(2i -1)/2 common edges between the spanning stars and 2i(n/2i) common edges between the inner vertices of T 1 , . . . , T 2i and the remaining vertices. Thus, there are i(n -1) common edges and by definition ℓ ≥ i(n -1).

Second, suppose n is odd. Let i = ⌊(ℓ/(n -1) + 1/2⌋. We begin by proving that dst 0,ℓ (K n ) < (n -1)/2 + i + 1 for 0 ≤ i < (n + 1)/2. Suppose that there are (n -1)/2 + i + 1 (0, ℓ)-disjoint spanning trees. By Corollary 5.2, we have

|E(K n )| ≥ ((n -1)/2 + i + 1)(n -1) -ℓ. Observe that ((n -1)/2 + i + 1)(n -1) -ℓ = n(n -1)/2 + i(n -1) + (n -1)/2 -ℓ. Since |E(K n )| = n(n -1)/2, we have ℓ ≥ i(n -1) + (n -1)/2,
contradicting the definition of i. We begin by constructing (n -1)/2 + i (0, ℓ)-disjoint spanning trees in K n , for 1 ≤ i ≤ (n + 1)/2. We construct two kinds of spanning trees. First, we construct 2i -1 spanning trees T 1 , . . . , T 2i-1 which are spanning stars. Second, we construct (n -1)/2i + 1 spanning trees in K n , each tree having two inner vertices, following the construction described in [START_REF] Matsushita | Completely independent spanning trees in (partial) k-trees[END_REF] (with disjoint inner vertices). There are (2i -1)(2i -2)/2 common edges between the spanning stars and (2i -1)((n -1)/2i) common edges between the inner vertices of T 1 , . . . , T 2i-1 and the remaining vertices. Thus, there are (2i -1)(i -1) + (2i -1)((n -1)/2i + 1) = i(n -1) -(n -1)/2 common edges and by definition ℓ ≥ i(n -1) -(n -1)/2.

The middle part of Figure 7 depicts three (0, 2)-disjoint spanning trees in K 5 . Proposition 6.5. Let n be a positive integer. For 1 ≤ ℓ < (n -1), we have dst 1,ℓ (K n ) ≤ ⌊n/2⌋ + ⌊ℓ/2 -1 even (n)/2⌋, where 1 even (n) = 1 if n is even, and 0 otherwise. Moreover, if ℓ ≥ (n -1), then dst 1,ℓ (K n ) is not finite.

Proof. Observe that a connected dominating set of K n can contain only one vertex. Thus, if ℓ ≥ (n -1), then dst 1,ℓ (K n ) is not finite.

First suppose n is even. Let i = ⌊ℓ/2-1/2⌋. We prove that we can construct

n/2 + i (1, ℓ)-disjoint spanning trees in K n , for 1 ≤ i ≤ n/2 -1. Let B be an induced K n-2(i+1) of G = K n .
We begin by creating n/2i -1 completely independent spanning trees T 1 , . . . , T n/2-i-1 in B, as in [START_REF] Matsushita | Completely independent spanning trees in (partial) k-trees[END_REF]. Let u be a vertex of G -B. We are going to extend these trees in order they span the whole graph G. To each tree T k , 1 ≤ k ≤ n/2i -1, we add the vertex u and an edge incident to u and to a vertex of I(T k ) ∩ B. We finally add to T k the edges incident to u and to every vertex of G -B. We now construct the remaining trees T ′ 1 , . . . , T ′ 2i+1 as follows. Each tree T ′ k , 1 ≤ k ≤ 2i + 1, has two inner vertices: u and a vertex u k of G -(B ∪ {u}) different for each tree. Each tree T ′ k also contains the edges incident to u and to every vertex of G -B and the edges incident to u k and to every vertex of B. It is easy to verify that the trees T 1 , . . . , T n/2-i-1 , T ′ 1 , . . . , T ′ 2i+1 have only one common vertex (the vertex u) and 2i + 1 = ℓ common edges (the edges incident to u in G -B).

Second, suppose n is odd. Let i = ⌊ℓ/2⌋. We prove that we can construct (n -1)/2 + i (1, ℓ)-disjoint spanning trees in K n , for 1 ≤ i ≤ (n -1)/2. Let B be an induced K n-2i-1 of K n . We begin by creating (n -1)/2i completely spanning trees T 1 , . . . , T (n-1)/2-i in B, as in [START_REF] Matsushita | Completely independent spanning trees in (partial) k-trees[END_REF] and extend them to the whole graph G as for the case n even. We construct the trees T ′ 1 , . . . , T ′ 2i similarly as in the case n even. It is easy to verify that the trees T 1 , . . . , T (n-1)/2-i , T ′ 1 , . . . , T ′ 2i have only one common vertex (the vertex u) and 2i common edges (the edges incident to u in G -B).

The right part of Figure 7 depicts four (1, 3)-disjoint spanning trees in K 6 . Note that we can obtain a lower bound on the number of (1, ℓ)-disjoint trees in K n by using Proposition 5.1. However, in this case, we do not obtain a tight bound. Moreover, Proposition 5.1 implies that dst i,0 (K n ) = ⌊n/2⌋ for every positive integer i.

Cylinders

Let n 1 and n 2 be positive integers with n 1 ≥ 3 and n 2 ≥ 3. Let V (C(n 1 , n 2 )) = {(i, j)| 0 ≤ i < n 1 , 0 ≤ j < n 2 } and E(C(n 1 , n 2 )) = {(i, j) (i ′ , j ′′ )| i = i ′ , j = j ′ ± 1 ∨ j = j ′ , |ii ′ | = 1 (mod n 1 )}. Theorem 8. There exist two (0, n 1 -2)-disjoint spanning trees in the cylinder C(n 1 , n 2 ).

Proof. We describe these two trees by giving their edge sets: E(T 1 ) = {(0, j)(0, j +1)| j ∈ {0, . . . , n 2 -2}}∪{(i, j)(i+1, j)| i ∈ {0, . . . , n 1 -2}, j ∈ {0, 2, 4, . . . , 2⌊(n 2 -1)/2⌋}} ∪ {(i, j)(i, j + 1)| i ∈ {1, . . . , n 1 -2}, j ∈ {0, 2, 4, . . . , 2⌊(n 2 -1)/2⌋}}∪{(0, j)(n 1 -1, j)| j ∈ {1, 3, 5, . . . , 2⌊(n 2 -2)/2⌋+1}}. E(T 2 ) = {(n 1 -1, j)(n 1 -1, j + 1)| j ∈ {0, . . . , n 2 -2}} ∪ {(i, j)(i + 1, j)| i ∈ {0, . . . , n 1 -2}, j ∈ {1, 3, 5, . . . , 2⌊(n 2 -2)/2⌋ + 1}} ∪ {(i, j)(i, j + 1)| i ∈ {1, . . . , n 1 -2}, j ∈ {1, 3, 5, . . . , 2⌊(n 2 -2)/2⌋ + 1}} ∪ {(0, j)(n 1 -1, j)| j ∈ {1, 3, 5, . . . , 2⌊(n 2 -1)/2⌋}} ∪ {(i, 0)(i, 1)| i ∈ {1, . . . , n 1 -2}}.

Observe that C(n 1 , n 2 ) contains 2n 1 n 2n 1 edges. Hence, by Corollary 5.2, we can conclude that there does not exist two (0, m)-disjoint spanning trees in C(n 1 , n 2 ), for m < n 1 -2.

square grids

Let n 1 and n 2 be positive integers with n 1 ≥ 3 and n 2 ≥ 3. Let V (G(n 1 , n 2 )) = {(i, j)| 0 ≤ i < n 1 , 0 ≤ j < n 2 } and E(G(n 1 , n 2 )) = {(i, j) (i ′ , j ′′ )| i = i ′ ± 1, j =

j ′ ∨ i = i ′ , i = j ′ ± 1}.
In two papers [START_REF] Fujie | An exact algorithm for the maximum leaf spanning tree problem[END_REF][START_REF] Li | Maximum Leaf Spanning Tree Problem for Grid Graphs[END_REF], the trees with a maximum number of leaves in G(n 1 , n 2 ) have been determined. In particular, Fujie [START_REF] Fujie | An exact algorithm for the maximum leaf spanning tree problem[END_REF] has shown that a spanning tree of G(n 1 , n 2 ) has at least ⌈n 1 n 2 /3⌉ inner vertices. Hartnell and Rall [START_REF] Hartnell | Connected Domatic Number in Planar Graphs[END_REF] have proven that there do not exist two disjoint connected dominating sets in G(n 1 , n 2 ), except if n 1 ≤ 2 or n 2 ≤ 2. However, this is not the case for 1-rooted connected dominating set. We finish this paper by giving a construction of two 1-rooted connected dominating sets in G(n 1 , n 2 ) for n 1 ≥ n 1 and n 2 ≥ 3. In Figure 9, we exhibit two trees induced by two 1-rooted connected dominating sets in G [START_REF] Fujie | An exact algorithm for the maximum leaf spanning tree problem[END_REF][START_REF] Hasunuma | Completely independent spanning trees in maximal planar graphs[END_REF]. In this example, we have minimized the number of common edges.

Open questions

In this introducing paper about (i, j)-disjoint spanning trees, we tried to cover a large number of issues. However, there still remains a lot of interesting prop- erties to be found about this notion. We finish this paper by giving some open questions:

1. Does there exist k (log k (n), 0)-disjoint spanning trees in every k-connected graph of order n?

2. Determine conditions in order to guarantee the existence of k completely independent spanning trees, k ≥ 3, in the square of graphs.

3. Determine conditions on chordal graphs in order to guarantee the existence of two disjoint connected dominating set.

4. Determine dst i,j (K n ) for the remaining cases.

5. Determine dst i,j for the complete k-partite graphs.

6. Determine the minimum number of common edges m in order to have two (1, m)-disjoint spanning trees in the square grid.

Figure 1 :

 1 Figure 1: Three disjoint connected dominating sets in C 3 P 4 (on the left) and the spanning trees induced by these dominating sets (on the right) (circles: D 1 or I(T 1 ); triangles: D 2 or I(T 2 ); squares: D 3 or I(T 3 ); plain lines: edges of T 1 ; dashed lines: edges of T 2 ; dotted lines: edges of T 3 ).

Figure 2

 2 Figure 2 illustrates an 1-rooted partition on a specific graph. Theorem 2. Let G be a graph. There exist k ℓ-rooted connected dominating sets D 1 , . . . , D k in G if and only if G has an ℓ-rooted partition into k + 1 sets.

Proposition 2 . 5 .

 25 There exist k ℓ-rooted connected dominating sets D 1 , . . . , D k in a graph G if and only if there exist a subset of vertices A ⊆ V (G) such that |A| ≤ ℓ and d c (G(k, A)) ≥ k.

Figure 3 :

 3 Figure 3: The graph H (on the left), the graph H ′ (on the middle) and the graph H + (on the right).

Figure 4 :

 4 Figure 4: Pattern to construct the trees in H (on the left), the graph H ′ (on the middle) and the graph H + (on the right) (simple line: edge of T 1 ; dashed line: edge of T 2 ; boxed vertices: inner vertices of both T 1 and T 2 ).

Proposition 4 . 1 .

 41 Let G be a graph and let T 1 , . . . , T k be (i, j)-disjoint spanning trees in G. For every subset of vertices A ⊆ V (G) such that |A| < k and G -A is not connected, (at least) one vertex of A is in I(T 1 , . . . T k ). For every subset of edges B ⊆ E(G) such that such that |B| < k and G -B is not connected, (at least) one edge of B is in E(T 1 , . . . T k ).

Definition 4 . 3 (

 43 [START_REF] Kriesell | Edge-disjoint trees containing some given vertices in a graph[END_REF]). Let k and ℓ be two integers such that ℓ ≥ k. Let G k,ℓ be the bipartite graph with vertex set {1, . . . , ℓ} ∪ {u A | A ⊆ {1, . . . ℓ}, |A| = k} and edge set {iu A

Proposition 4 . 4 .

 44 There exist two disjoint connected dominating sets in C 4 and three disjoint connected dominating sets in K 3,3

A 1 ]Figure 5 :

 15 Figure 5: Disjoint connected dominating sets in C 4 (on the left) and in K 3,3 (on the right) (circles: D 1 ; triangles: D 2 ; squares: D 3 ).

Figure 6 :

 6 Figure 6: The graph P * 6 (on the left) and the graph P - 6 (on the right).

  illustrates the graph P * n for n = 6. Proposition 5.5. Let n ≥ 5. For any two disjoint connected dominating sets D 1 and D 2 in P * n , ||D 1 | -|D 2 || ≥ n -5. Proof. Suppose without loss of generality that u / ∈ D 1 . Since D 1 should be connected, it should contain consecutive vertices of P n . Moreover, since D 1 should be dominating, it should contain every vertex of P n , except its extremities. Thus, |D 1 | ≥ n -2 and consequently |D 2 | ≤ 3. Therefore, we have ||D 1 | -|D 2 || ≥ n -5.

Theorem 7 .

 7 Let k ≥ 2 be an integer. Every k-connected interval graph G satisfies d c (G) ≥ k.

Figure 7 :

 7 Figure 7: Three completely independent spanning trees of K 6 (on the left), three (0, 2)-disjoint spanning trees of K 5 (on the middle) and four (1, 3)-disjoint spanning trees of K 6 (on the right) (thin line: edge of T 4 ; hexagon: I(T 4 ); pentagon: I(T 1 ) ∩ I(T 2 ) ∩ I(T 3 ) ∩ I(T 4 )).

then we set x n i = x n- 1 i

 1 , otherwise we set to x n i a vertex not in (X n ∩X n+1 ∩{x n 1 , . . . , x n k })\{x n-1 i }. Such a vertex exists since otherwise it would imply that |X n ∩ X n+1 | < k. Finally, the sets D 1 = ∪ 1≤j≤n {x j 1 }, . . . , D k = ∪ 1≤j≤n {x j k } are disjoint connected dominating sets on the graph G[X 1 ∪ . . . ∪ X n+1 ]. Consequently, by induction, we can construct k disjoint connected dominating sets on the graph G.

Figure 8 :

 8 Figure 8: Two (0, 3)-disjoint spanning trees of C(5, 6).

Theorem 9 .

 9 There exist two 1-rooted connected dominating sets in the grid G(n 1 , n 2 ), for every n 1 ≥ 3 and n 2 ≥ 3.Proof. Suppose without loss of generality that n 1 ≤ n 2 . If n 1 = 3, then one can easily construct two 1-rooted connected dominating sets by settingD 1 = {(1, j)|j ∈ {0, . . . , n 2 -1}} and by setting D 2 = V (G(3, n 2 )) \ D 1 ∪ {(1, 0)}.Now suppose that n 1 ≥ 4. We construct D 1 as follows:D 1 = {(0, i)| i ∈ {0, . . . , n 2 -1}}∪{(n 1 -1-2i, j)| i ∈ {0, . . . , ⌊(n 1 +1)/4⌋}, 2i+ 1 ≤ j ≤ n 2 -2 -2i} ∪{(2 + 2i, j)| i ∈ {0, . . . , ⌊(n 1 -1)/4⌋}, 2i + 1 ≤ j ≤ n 2 -4 -2i} ∪ {(i, 1 + 2j)| 2j + 2 ≤ i ≤ n 1 -1 -2j, j ∈ {0, . . . , ⌊n 1 /4⌋} ∪ {(i, n 2 -2 -2j)| 2j ≤ i ≤ n 1 -1 -2j, j ∈ {0, . . . , ⌊(n 1 + 2)/4⌋}. The set D 2 is V (G(n 1 , n 2 ))\D 1 ∪{(1, n 2 -2)}. Note that D 1 ∩D 2 = {(1, n 2 -2)}.

Figure 9

 9 illustrates this construction, with circle vertices corresponding to D 1 and triangles to D 2 (the square vertex being both in D 1 and D 2 ).

Figure 9 :

 9 Figure 9: Two (1, 18)-disjoint spanning trees of G(7, 13).


Prof. Dr Silke Weidner

Juliane Ribbeck

Professeur Laurent Guihéry
email: laurent.guihery@u-cergy.fr

Wissensnetzwerk Stadt und Handel Stationär und online -HANDEL in der STADT -2014 -2016 Herausgegeben von Fachgebiet

Keywords: Obvious, Environmental friendly, Good acceptability, Winnerwinner

come

neighborhood. Local politicians and public policy designers have integrated these projects in new urban plans and future city modelling (Lyon for instance with a new urban consolidation center starting in 2012 around Cordeliers area). On the side of the business' actors, shippers, transport companies, distributors, gain in efficiency and cost reduction can be achieved. Quality of service can be improved too: more frequency, more services with high load factor in trucks, which can have an impact on costs too. Do we face a "happy winner -winner organization" for all member of the urban club? How are the gains shared between all the members of the urban club? Does this system keep a good level of innovation in transport and logistics companies? Is it sustainable in a long term perspective, facing different modal alternatives, rail for instance? Do we have to take into account the long term impact on innovation and possible distortion of competition and cartelization? Few contributions are investigating these issues. Even if the objectives are obvious for the quality of city life and policy action against pollution, we have to think of the implication of such a decision on economic activities in a larger perspective than the city scale, on the motor of innovation in the transport sector and on the power of competition to pressure costs -for the benefit of the customers and taxpayers -and limit rent seeking and cartels opportunities. We also have to analyze the recommendation towards the pooling of logistics and trucking activities in cities, especially if these recommendations imply a burden of public budget through subsidies, which can mean a future increase of taxes for the taxpayers. From the beginning, the idea of pooling strategies is challenging the basic economic theory, because it suggests a complex trade-off between competition and institutional organization of the market in a winnerwinner perspective for all actors of the urban clubs.

A great winner -winner idea at first glance?

On one hand, it is a necessity now, for environmental objectives and quality of life but also in terms of efficiency, to limit the freedom of trucks entering city centers for delivering products. But we need to act very carefully and make no mistakes in these new policy designs. Cities are now representing 50 % of the world population -and 75 % in France. They are key players of social and economic life, especially in Europe where there is a long tradition of urban analysis and comparison between Member States of the European Union2 . Cities are now facing huge up-to-date issues: sustainable development balancing competitiveness/business and quality of life/protection of the environment. Transport plays a key role but city action is facing today scarcity of public finance, unemployment and social matters (exclusion, ghettos, inequalities, poverty, sometimes riots). Learning from each other is a key success factor for further development toward sustainable cities [START_REF] Guihery | Urban action in ERDF in France and Germany (2007-2013) : what learning for the next programming of regional structural funds ?[END_REF]. And transferring experiences at the level of the European Union could be a good mean to improve the quality of life of European citizen in a "best practice" strategy. Pooling strategies, linked with city logistics strategies, have to be understood in this way.

The city at the cornerstone of transport, business, quality of life and dynamism

The urban analysis among researchers, from city planners to economists and urban scientists, has now investigated the evolutions of urban dynamism, mainly from a more sceptical point of view than in the seventies: increase of car mobility which leads to pollution and scarcity of space in urban areas, urban sprawl which implies huge environmental damages, but also social damages of spatial exclusion in a long term perspective are on the agenda of city scientists. City logistics is coming from this evolution. Urban thinking towards sustainable development started in Stockholm in 1972, which is not surprising if you consider the experience of Scandinavian countries in environmental analysis. In June 1990, the European Commission delivered its first Green Book towards urban development and Environment. This report is showing a clear European experience and history towards "urban culture" and a good level of cooperation between cities. In Rio in 1992, the agenda 21 adopted by 173 chiefs of state and governments is highlighting the crucial role of urban sustainable development. In 1994, the Charta of Aalborg, the European Conference on sustainable cities, is considering cities as a key actor for implementing policies against environmental damages. In March 1996, a report is published giving us some definition how it can work: refusal of a too centralized top down approach and interest in a bottom up approach. Then the famous Charta of Leipzig was adopted in May 2007 and focused on integrated urban development and less developed suburbs. But the Charta of Leipzig is also proposing tools to achieve these goals on a European level, which asks for policy action and recommendations. In Marseille in November 2008, the ministers in charge of urban development of the European Union discussed on "sustainability and solidarity in cities" and have proposed a common framework to get in more operational actions : "Reference framework for sustainable cities", which will be available in 2011. In Tolede, on the 21st and 22nd of June 2010, a meeting of the European Ministers in charge of urban action and housing has highlighted again the role of the Urban Integrated Plan (Declaration of Tolede). All these elements are showing the large agreement on urban sustainable development and are expressing, once again, the importance and the relevance of European Community spirit. Key elements are urban management and co-management, political integration, cooperation and partnership. We can integrate the thinking of an environmentally friendly freight transport system in cities and complex interactions with urban passenger transport, quality of services in cities in this perspective.

City logistics and pooling strategies: obvious, great and acceptable…

The idea of pooling strategies is, from the beginning, obvious and welcomed. It refers to basic human behavior where living in community, sharing goods and services, connecting with people and institutions, having a social life are common roots of human being (Tversky A. et Kahneman D., 1979 3 ). It offers an optimization of freight deliveries in the city, sometimes less costly than a decentralized organization of urban freight transport4 . It is compatible with the sustainable development strategies of European member states and implemented in cities. To remember, the new objectives of the environmental policy of the E.U. are impressive (see results of the European Union meeting of October, 24 th , 2014):

-Reducing greenhouse effects by 40 % until 2030, comparing to 1990 (last target was 20 % toward 2030) -Renewable energy must reach at least 27% of the energy mix (20 % in the previous target) -27 % of the energy saving (20 % in the previous target)

In a theoretical perspective, we can find some interesting inputs from the transaction costs theory (Coase, 1937, Willimason, 1985) that supports the idea of integrating the transport and distributor sector in cities. This can help to understand the relevancy of pooling: integrating different companies will reduce asymmetry in information and improve global efficiency through a better transfer of knowledge and information. But this theory is mainly focused on an intra-firm analysis, we face here a complex issue of links between different companies, sometimes in competition on other segments of markets.

Pooling is benefiting at the same time from scale and scope economies [START_REF] Curien | Economie des Reseaux[END_REF], but also from indirect and direct club externalities [START_REF] Buchanan | the Calculus of Consent: Logical Foundations of Constitutional Democracy[END_REF][START_REF] Charles | The Political Economy of Rent-Seeking[END_REF]. The integration of transport companies in a large platform will generate scale economies (high load factor of trucks) but also scope economies (integration of different services in the same tour). In a first analysis, every member of the club is benefiting from knowledge from the others: direct club externalities. The success of the organization will generate indirect club externalities: improvement of the services and ideas of new services, increase of warehousing, implementation of new solutions.

It implies the participation of a lot of actors, from private operators to city authorities and local agencies: this mix of actors seems "perfect" from a first analysis but our analysis will try to look more deeply in the relevancy of this mix of actors, especially if such strategies are linked with a lock-in of the market of delivery in cities [START_REF] Schulte | Information Rules: A Strategic Guide to the Network Economy Tversky A[END_REF], looking for rent seeking at the cost of the local citizens -taxpayers and creating cartels.

In cities, strategies of pooling and logistics platform are obvious. The importance of the shipping of small parcels, the increase in delivery for e-commerce, the new strategies of retails and department stores of limiting stocks -in the current time period of financial constraints and an economic crisis in the South of Europe, and France -means new strategies for logistics and transport5 . The cost of land property, cost constraints, the issue of congestion -lack of investment in new infrastructures due to scarcity of public money-are motors for developing strategies of pooling. Today researchers assessed that 10 % of the traffic in cities is linked with city logistics transport [START_REF] Schulte | Information Rules: A Strategic Guide to the Network Economy Tversky A[END_REF]. And 2/3 of the deliveries occurs between 8h and 12h. Some products are excluded from these strategies: chemical products but also food, fresh and frozen products, which have a good perspective for development. One of the main resistances for pooling of transport is the mentality of actors, which is complicated to change and to convince. Everyone must be ready to make concessions to find an agreement between the actors, which is not easy. Transport companies are very sensitive with respect to this issue, which is also linked with freedom of business, free mobility and free opportunities.

On the opposite, it also seems that acceptability from the population for implementing city logistics strategies is quite good. Nevertheless some neighbors could be opposed to a launch of a logistics platform near their home. The access of pedestrians' areas, often an issue for delivery, can be solved by transferring parcels to soft mode dedicated solutions.

We seem then to face a win-win strategy between urban population, politicians and actors for logistics and transport. Why then thinking further of this issue?

Limiting freedom of mobility in cities: the need of strong justifications

Concerning the free access to city, strong justifications have to be proposed. Free mobility in is one of the foundations of modern democracies and every limitation of free mobility has to be justified in deep and clear argumentations, even for trucks. If some limitations of free mobility have to be proposed, some exemptions have to be proposed, for example facing cultural events in cities where trucks are welcomed for delivering music stages and open air festival infrastructures. If removing single and small trucks implies delays in delivering, increase in cost, or a lack of quality of service (because of a lack of competition among the actors of the urban freight delivery club), we can question the relevancy of pooling and transport logistics in a long term perspective.

We also have to integrate the possibility of innovation in the trucking sector, such as electric delivering vehicles that can freely enter the city, because they are not as huge as carbon motorized trucks and are often silent running. We often forget in the analysis to integrate the motor of innovation in the thinking of transport on a certain period of time, which is fixed and given in terms of transport. But as we know from history and Behavioral Economics, it can change rapidly.

If a complex organization of logistics and delivery in cities implies a limitation of innovation, the setting up of barriers to entry and the justification of grandfather rights, we can put some doubt on the success of the policies in a long term perspective, even if, in a short time, it implies an improvement of the level of congestion and quality of life because of less emission in the cities.

Following points have to be discussed within the scientific community:

City logistic and pooling: a way for getting more subsidies in the transport system?

The first point concerns the use of subsidies for implementing such solutions. Some experimentations and case studies show that such a platform can be implemented without subsidies: the Nurnberg I.S.O.L.D.E. GVZ (UCC in German) for example was established without subsidies [START_REF] Schulte | Information Rules: A Strategic Guide to the Network Economy Tversky A[END_REF]. It seems relevant to start from this perspective for implementing logistics platforms in cities: logisticians, transport companies and maybe customers6 should cover the cost of this new infrastructure in cities. Following the principle of equivalence in Public Finance theory [START_REF] Musgrave | Public Finance[END_REF], users who benefit from the infrastructure should cover the costs. This result is linked with the recommendation that transport must cover its social costs, it means private costs and external negative costs, especially for road freight transport (White Paper, 2011). On this issue, we also have to think in terms of spillovers of this new platform: who is benefiting? We have then to adjust the cost of the financing with the spillover of the platform on the urban scale (user-payer principle).

Pooling strategies: motor for more innovation or braking innovation?

The main motor of customer satisfaction is innovation. Incentives towards more innovation in the transport sector, for more environmentally friendly transport, should be at the center of the recommendation of experts and public policy designers facing the issue of pooling. Strong incentives in this direction have to be imposed to the logistics platform : the 2014 Nobel Prize in Economics was awarded in 2014 to Jean Tirole precisely because of his work on modern measures for putting efficiency pressures on a monopoly -because logistics platforms will be a type of monopoly in the end. Will a UCC be the place of sparkling innovation? Information technologies are the cornerstone of success of these development but it is also needed that integration of Information Systems should be strictly limited to supply chain data and not linked with data on cost of production, which can have an impact on the level of competition and can open the door to cartelization and then control and enforcement of anti-trusts authorities.

Competition for the market, intermodal competition, spatial competition: three motors of pooling and city logistics?

All experts on these issues consider that competition for the market -tender for the management of this city logistics platform -is a key issue for strong incentives on cost efficiency and quality of services. They recommend a period of time of three years before a new tender will be launched. The rules of transparency and fairness for such a call must be clear and enforced. As we have noticed, transport activities in cities -non-discrimination in the quality of service, respect of privacy of parcels, independency, few barrier to entry -is part of "the freedom endowment" of each citizen and strong control and protection must be enforced. Why not setting up a regulating agency in charge of controlling the market power of the logistic platform?

In this perspective, new researches are launched to examine the relevancy of railway freight transport in urban areas (De Langhe K., 2014): the idea is to think intermodal in urban freight transport systems. Cities are looking with great interest at the local railway network and try to assess, with the infrastructure manager, the level of congestion on this network, to see if tracks are available for implementing freight trains for delivering urban city centers. In Brussels for instance there is 163 km of railway tracks that could maybe be used (Lebeau P., Macharis, C., 2014, p. 9). Tramway networks are also used in this perspective (the famous Dresden case, Tramfret Paris).

The dynamism of the research is linked with the different packages of the Railway Reform managed by the European Union, based on the split between the infrastructure manager and service operations. This opportunities allow newcomers to enter the market with lean business models for new freight train operations, for example in the urban area. In France, governmental programs are supporting « Opérateurs Frets de Proximité » (OFP). We can fancy that some rail freight transport operations will start in cities.

In many cities, rivers and waterways are part of cultural and historical heritage7 . Intermodal transport has to be developed using waterways for freight transport and for delivering urban business actors. This is the case for Paris (Franprix managed by Norbert Dentressangle8 ).

Intermodal competition could then occur within the city between road freight transport, urban railway transport and waterway transport.

We can finally investigate the relevance of supporting spatial competition between different urban logistic platforms. Such a strategy could improve the level of quality of service and push logistics operators and transport companies towards more innovation, both in services and transport technology. Why not suggesting to city planners and local politicians to implement two or three pooling platforms and open some spatial competition among them, for reverse logistics too.

One of the main objectives for urban transport policy both for passenger and freight is achieving seamless transport that means reducing time of interconnection and improving these interconnections (European Union, 2011). This is obvious for passenger transport but this should also be the main objective of city logistic policy design: it is not easy for freight, as parcels are dispatched in a very complex system of sub delivering and logistics.

And what can happen if local politicians, local transport companies and distributors decide to lock-in the system?

Setting up an organization between shippers, transport companies, logisticians, supported by local authorities, needs a clear and rigorous analysis.

As transport in cities is one element of crucial importance -basic endowment of freedombecause it deals with our privacy, connects citizens and companies with the others and fosters projects, business and opportunities, it is very important to try to analyze all the implications of local decision of pooling and city logistics.

The first question to try to answer is the impact on competition, which has for objectives to limit the costs of service production for the citizens-taxpayers but also to provide different "sources" of transport and logistics services. It is also a way to guarantee free access to transport services, and multimodal competition in this perspective could be a good way to maintain a good level of prices and quality if services but also incentives towards innovation and differentiation. A clear contract must be signed among the actors, fair tender has to be organized -for instance every three years -and barriers to entry have to be removed. The issue of sunk costs and free access to essential facilities (see the debates on Essential Facilities Doctrine) also have to be analyzed, in order to avoid lock-in strategies [START_REF] Schulte | Information Rules: A Strategic Guide to the Network Economy Tversky A[END_REF]. Nondiscrimination, welcoming newcomers are core elements of the success of the project in a long term perspective. All these basic results of industrial economics suggest the setting up of a regulating agency, linked with a competition authority or anti-trust policy with having an overview of the solution and system implemented locally. We suggest representatives of the central state on the board of this regulating agency and representatives of the European Union for clear transparency in tender procedures.

The second question refers to the level of jurisdiction which is better suited for implementing such a solution: local, regional or national? Following the fiscal federalism theory [START_REF] Oates | Fiscal federalism[END_REF], we can suggest that local authorities must be at the center of the organization. But as Rodden and alii ( 2004) noticed, we have to be careful of irresponsibility at policy design at local level, because of a lack of expertise and long term view: overspending, unlimited use of subsidies, local social networking which brings inefficient results and services, rent seeking strategies, corruption and club strategies, are possible and must be controlled. As expressed before, why not integrating regional authorities, even national and European Union representatives, but also regulating agency representatives, competition authority representatives in the board of such an Urban Consolidation Center?

The last point concerns the open door to corruption in such a locked system [START_REF] Frédéric | Regulatory Capture Revisited -Lessons from Economics of Corruption[END_REF]. What can happen if local politicians connected with local transport companies limit the access to the market to newcomers and new companies, then limiting innovation? What happens if local networks of transport service providers control the information of all shipping, parcels and deliveries within the cities, and are connected with local politicians? On this issue, it is up to the citizens and all actors of public life to remain watchful to protect our rights and freedom.

Conclusion: city logistics 2.0 and beyond: urban tolling maybe?

Beyond the development of city-logistic platforms, we can imagine a direct collaborative synergy 2.0 between shippers and customers. Customers could organize on their own the delivery of parcels, using all modes of transport available through social network and collaborative networking. Next research would maybe investigate this issue of City Logistics 2.0 where all actors are implemented and will participate, from taxi drivers, local public transport to pedestrians on the go between a shop and a delivery point.

There is also interesting synergies to notice in a common development of logistic platform and the introduction of urban tolling systems. Next researches could be welcomed to develop this point.

For example, in 1909, Victor Cambon, French Ingenieur travelling often in Germany, was comparing, in his book -Cambon V., l'Allemagne au travail, 1909 -the city of Leipzig and the city of…. Lyon, in terms of public goods, public finance, transport networks, high education and economic activities.

The Behavioral Economics research program (Nobel Prize in Economics for Kahneman in 2001) has developed interesting researches in the field of transport.

Alain Borri (BP2R, promoter ("parrain de promotion") of the Master degree TLIC in 2013-2014), one of the leading experts in France for proposing pooling strategies in the transport sector (not mainly in the urban field), often in the relation between producers and distributors, has assessed that the benefit is between 15 and 30 % in costs reductions.

Can we argue maybe that pooling strategies are a child of the economic crisis?

Fair pricing in the transport system implies that all actors cover the social cost of transport (White Paper, 2011): private and external costs, mainly negative for road freight transport. There are few justifications in the economic theory of putting transport costs equal to 0 in the B2C business.

Lyon is interesting in this perspective (Rhône, Saone).

Experts are considering that Norbert Dentressangle is losing money in this business but the impact in terms of communication -greening the city -is quite good.