Almost disjoint spanning trees

Benoit Darties, Nicolas Gastineau and Olivier Togni LE2I UMR6306, CNRS, Arts et Métiers, Univ. Bourgogne Franche-Comté, F-21000 Dijon, France

Extended Abstract

In this extended abstract, we only consider connected graphs. Let k ≥ 2 be an integer and T 1 , . . . , T k be spanning trees in a graph G. A vertex is said to be an inner vertex in a tree T if it has degree at least 2 in T . We denote by I(T ) the set of inner vertices of tree T . The spanning trees T 1 , . . . , T k are completely independent spanning trees if any vertex from G is an inner vertex in at most one tree among T 1 , . . . , T k and the trees T 1 , . . . , T k are pairwise edge-disjoint.

Completely independent spanning trees were introduced by Hasunuma [START_REF] Hasunuma | Completely independent spanning trees in the underlying graph of line graph[END_REF] and then have been studied on different classes of graphs, such as underlying graphs of line graphs [START_REF] Hasunuma | Completely independent spanning trees in the underlying graph of line graph[END_REF], maximal planar graphs [START_REF] Hasunuma | Completely independent spanning trees in maximal planar graphs[END_REF], Cartesian product of two cycles [START_REF] Hasunuma | Completely independent spanning trees in torus networks[END_REF] and k-trees [START_REF] Matsushita | Completely independent spanning trees in (partial) k-trees[END_REF]. Moreover, determining if there exist two completely independent spanning trees in a graph G is a NPhard problem [START_REF] Hasunuma | Completely independent spanning trees in maximal planar graphs[END_REF]. Recently, sufficient conditions inspired by the sufficient conditions for hamiltonicity have been determined in order to guarantee the existence of several completely independent spanning trees: Dirac's condition [START_REF] Araki | Dirac's condition for completely independent spanning trees[END_REF] and Ore's condition [START_REF] Fan | Ore's condition for completely independent spanning trees[END_REF]. Moreover, Dirac's condition has been generalized to more than two trees [START_REF] Hasunuma | Minimum degree conditions and optimal graphs for completely independent spanning trees[END_REF].

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

I(T 1 , . . . , T k ) = {u ∈ V (G)|∃ , u ∈ I(T ) ∩ I(T ), 1 ≤ <
≤ k} be the set of vertices which are inner vertices in at least two spanning trees among T 1 , . . . , T k , and we let E(T 1 , . . . , T k ) = {e ∈ E(G)|∃ , , 1 ≤ < ≤ k, e ∈ E(T ) ∩ E(T )} 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:

i) |I(T 1 , . . . , T k )| ≤ i; ii) |E(T 1 , . . . , T k )| ≤ j.
The sets D 1 , . . . D k in a graph G are disjoint connected dominating sets if they are pairwise disjoint and dominating. Moreover, if | ∪ 1≤i<j≤k D i ∩ D j | ≤ we say that D 1 , . . . D k are -rooted connected dominating sets. Other works on disjoint spanning trees are about disjoint connected dominating sets (the disjoint connected dominating sets can be used to provide the inner vertices of (0, E(G))-disjoint spanning trees). The maximum number of disjoint connected dominating sets in a graph G is the connected domatic number [START_REF] Zelinka | Connected domatic Number of a graph[END_REF]. 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] Wan | Distributed construction of connected dominating set in wireless ad hoc networks[END_REF]. Connected dominating sets are used to create a virtual backbone or spine of a wireless ad-hoc network.

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. Also, (0, * )disjoint spanning trees are related to connected dominating sets. Hence, we call them trees induced by disjoint connected dominating sets. For the same reason than (0, * )-disjoint spanning trees, ( , * )-disjoint spanning trees are trees induced by -rooted connected dominating sets. In the following sections, we illustrate that (i, j)-disjoint spanning trees provide some nuances between the existence of disjoint connected dominating sets and of completely independent spanning trees.

Characterizations in terms of partitions

We introduce a definition which is a generalization of CIST-partition introduced by Araki [START_REF] Araki | Dirac's condition for completely independent spanning trees[END_REF]. Let V 1 and V 2 be two disjoint 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 }. 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.
Theorem 1.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 build (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 now, we suppose that E(T i ) is empty and we progressively add edges in E(T i ), for each integer i, 1 ≤ i ≤ k, in order to obtain spanning trees of G. Since G[V i ] is connected for each i, 1 ≤ i ≤ k, we can add edges in E(T i ) in order to form a tree with vertex set V i , for each 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 one edge e of D i,j with extremity

u in E(T 1 , . . . , T k ). Let D d i,j (u) = {v ∈ V (D i,j )| d Di,j (u, v) = d}.
We add the following edges to E(T 1 ):

{vv ∈ E(D i,j )| v ∈ D d i,j (u), v ∈ D d+1 i,j (u), d is even} and the following edges to E(T 2 ): {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,j -e. We define D d i,j (u) as follows: {v ∈ V (D i,j )| d Ti,j (u, v) = d}. We add the following edges to E(T 1 ):

{vv ∈ E(T i,j )| v ∈ D d i,j (u), v ∈ D d+1 i,j (u), d is even} and the following edges to E(T 2 ): {vv ∈ E(T i,j )| v ∈ D d i,j (u), v ∈ D d+1 i,j (u), d is odd} ∪ {e}.
Note that e ∈ E(T 1 , . . . , T k ). We repeat this process for every connected component of B(V i , V j ) and every integers i and j, 1 ≤ i < j ≤ k. Since we have 1≤i<j≤k c i,j ≤ , the set E(T 1 , . . . , T k ) contains at most edge. 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 for which they have a neighbor. 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 . We have a contradiction since u has no neighbor in I(T j ) and T j is supposed to be a spanning tree. 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 contains |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 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 each connected component of B(V i , V j ) which is a tree, we need an edge in E(T 1 , . . . , T k ). Thus, we obtain a contradiction since we obtain trees which are not (0, )-disjoint spanning trees and Property iii) follows.

For a graph G and 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. An -rooted partition of a graph

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 i, 1 ≤ i ≤ k; ii) B(V i , V j ) -N (A) contains no isolated vertex, for every i and j, 1 ≤ i < j ≤ k.

Computational complexity and connectivity

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 2.1 Let i and j be non negative integers. The problem 2-(i, j)-DSP is a NPcomplete problem for every pair of integers (i, j).

Sketch of proof.

The proof uses a reduction from 3-SAT similar to the reduction used by Hasunuma [START_REF] Hasunuma | Completely independent spanning trees in maximal planar graphs[END_REF].

Moreover, 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 k-connected graph, for k sufficiently large, contains at least two (i, j)-disjoint spanning trees or not. Theorem 2.2 Let i, j and k be integers. For any positive integer k, there exist a k-connected graph which does not contain two (i, j)-disjoint spanning trees. Sketch of proof. The considered graphs are the same than the graphs introduced by Kriesell [START_REF] Kriesell | Edge-disjoint trees containing some given vertices in a graph[END_REF] (they are the incidence graphs of complete k-uniform hypergraphs). The proof consists in proving that the existence of two (i, j)-disjoint spanning trees implies that there exists a vertex u in this graph for which the vertices of N (u) are all inner vertices of the same tree. Moreover, no vertex of N (u) should be inner vertex of both trees. These facts imply that u cannot be in one of the two spanning trees and thus a contradiction.

Some simple classes of graphs

We finish this extended abstract by giving some results for square of graphs, complete graphs and square grids. Theorem 3.1 Let G be graph. There exists two (0, 1)-disjoint spanning trees in G 2 and there do not exist two completely independent spanning trees in G 2 if and only if G is a tree from the family described by Araki [START_REF] Araki | Dirac's condition for completely independent spanning trees[END_REF]. Sketch of proof. Let V 1 and V 2 be the set of vertices induced by a bipartition of a spanning tree of G. It easy to prove that V 1 and V 2 form a 1-CIST-partition of G. Moreover, Araki has characterized the trees containing two completely independent spanning trees. It suffice to prove that a connected graph G which is not a tree contains two completely independent spanning trees to complete the proof. That is the case since the set of vertices induced by a bipartition of a spanning tree of G -{e} for e an edge of a cycle of G, is a 0-CIST-partition.

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] and that there does not exist two disjoint connected dominating sets in a sufficiently large square grid [START_REF] Hartnell | Connected Domatic Number in Planar Graphs[END_REF]. We give the following intermediate result about (i, j)-disjoint spanning trees (the proof is not given): Theorem 3.2 Let n be an integer. There are at most n/2 +max( /(n-1)+1 odd (n)/2 , n/2 ) (0, )-disjoint spanning trees in K n , where 1 odd (n) = 1 if n is odd and 0 otherwise. Also, there exist two 1-rooted connected dominating sets in P n1 P n2 , for every n 1 ≥ 3 and n 2 ≥ 3.

Theorem 1 . 2

 12 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. Sketch of Proof. The proof is similar to the one of Theorem1.1.