Keywords: traffic grooming, SONET ADM, optical networks, graph decomposition, design theory

Drop cost and wavelength optimal two-period grooming with ratio 4

Introduction

Traffic grooming is the generic term for packing low rate signals into higher speed streams (see the surveys [START_REF] Bermond | The CRC Handbook of Combinatorial Designs[END_REF][START_REF] Dutta | Traffic grooming in WDM networks : Past and future[END_REF][START_REF] Modiano | Traffic grooming in WDM networks[END_REF][START_REF] Simmons | Quantifying the benefit of wavelength add-drop in wdm rings with distance-independent and dependent traffic[END_REF][START_REF] Zhu | A review of traffic grooming in WDM optical networks : Architectures and challenges[END_REF]). By using traffic grooming, one can bypass the electronics in the nodes which are not sources or destinations of traffic, and therefore reduce the cost of the network. Here we consider unidirectional SONET/WDM ring networks. In that case, the routing is unique and we have to assign to each request between two nodes a wavelength and some bandwidth on this wavelength. If the traffic is uniform and if a given wavelength has capacity for at least C requests, we can assign to each request at most 1 C of the bandwidth. C is known as the grooming ratio or the grooming factor. Furthermore if the traffic requirement is symmetric, it can be easily shown (by exchanging wavelengths) that there always exists an optimal solution in which the same wavelength is given to each pair of symmetric requests. Thus without loss of generality we assign to each pair of symmetric requests, called a circle, the same wavelength. Then each circle uses 1 C of the bandwidth in the whole ring. If the two end-nodes of a circle are i and j, we need one ADM at node i and one at node j. The main point is that if two requests have a common end-node, they can share an ADM if they are assigned the same wavelength. For example, suppose that we have symmetric requests between nodes 1 and 2, and also between 2 and 3. If they are assigned two different wavelengths, then we need 4 ADMs, whereas if they are assigned the same wavelength we need only 3 ADMs.

The so called traffic grooming problem consists in minimizing the total number of ADMs to be used, in order to reduce the overall cost of the network.

Suppose we have a ring with 4 nodes {0, 1, 2, 3} and all-to-all uniform traffic. There are therefore 6 circles (pairs of symmetric requests) {i, j} for 0 ≤ i < j ≤ 3. If there is no grooming we need 6 wavelengths (one per circle) and a total of 12 ADMs. If we have a grooming factor C = 2, we can put on the same wavelength two circles, using 3 or 4 ADMs according to whether they share an end-node or not. For example we can put together {1, 2} and {2, 3} on one wavelength ; {1, 3} and {3, 4} on a second wavelength, and {1, 4} and {2, 4} on a third one, for a total of 9 ADMs. If we allow a grooming factor C = 3, we can use only 2 wavelengths. If we put together on one wavelength {1, 2}, {2, 3}, and {3, 4} and on the other one {1, 3}, {2, 4}, and {1, 4} we need 8 ADMs (solution a) ; but we can do better by putting on the first wavelength {1, 2}, {2, 3} and {1, 3} and on the second one {1, 4}, {2, 4} and {3, 4}, using 7 ADMs (solution b).

Here we study the problem for a unidirectional SONET ring with n nodes, grooming ratio C, and all-to-all uniform unitary traffic. This problem has been modeled as a graph partition problem in both [START_REF] Bermond | Traffic grooming in unidirectional WDM ring networks using design theory[END_REF] and [START_REF] Goldschmidt | The sonet edge-partition problem[END_REF]. In the all-to-all case the set of requests is modelled by the complete graph K n . To a wavelength k is associated a subgraph B k in which each edge corresponds to a pair of symmetric requests (that is, a circle) and each node to an ADM. The grooming constraint, i.e. the fact that a wavelength can carry at most C requests, corresponds to the fact that the number of edges |E(B k )| of each subgraph B k is at most C. The cost corresponds to the total number of vertices used in the subgraphs, and the objective is therefore to minimize this number.

Traffic Grooming in the Ring

Input : Two integers n and C.

Output : Partition E(K n ) into subgraphs B k , 1 ≤ k ≤ Λ, s.t. |E(B k )| ≤ C for all k.
Objective : Minimize Λ k=1 |V(B k )|. In the example above with n = 4 and C = 3, solution a consists of a decomposition of K 4 into two paths with four vertices [START_REF] Bermond | Minimizing SONET ADMs in unidirectional WDM rings with grooming ratio 3[END_REF][START_REF] Bermond | Traffic grooming in unidirectional WDM rings with grooming ratio C = 6[END_REF][START_REF] Bermond | Grooming in unidirectional rings : K 4e designs[END_REF][START_REF] Bermond | Traffic grooming in unidirectional WDM ring networks using design theory[END_REF] and [START_REF] Bermond | Traffic grooming in unidirectional WDM rings with grooming ratio C = 6[END_REF][START_REF] Bermond | Traffic grooming in unidirectional WDM ring networks using design theory[END_REF][START_REF] Bermond | Minimizing SONET ADMs in unidirectional WDM rings with grooming ratio 3[END_REF][START_REF] Bermond | Grooming in unidirectional rings : K 4e designs[END_REF], while solution b corresponds to a decomposition into a triangle (1, 2, 3) and a star with the edges {1, 4}, {2, 4}, and {3, 4}.

With the all-to-all set of requests, optimal constructions for a given grooming ratio C have been obtained using tools of graph and design theory [START_REF]Handbook of combinatorial designs[END_REF], in particular for grooming ratio [START_REF] Colbourn | Minimizing SONET ADMs in unidirectional WDM rings with grooming ratio 7[END_REF] and C ≥ N(N -1)/6 [START_REF] Bermond | Traffic Grooming in Unidirectional WDM Ring Networks : the all-to-all unitary case[END_REF].

C = 3 [1], C = 4 [4, 21], C = 5 [3], C = 6 [2], C = 7
Graph decompositions have been extensively studied for other reasons as well. See [START_REF] Bryant | A survey on the existence of G-designs[END_REF] for an excellent survey, [START_REF] Colbourn | Triple systems[END_REF] for relevant material on designs with blocksize three, and [START_REF]Handbook of combinatorial designs[END_REF] for terminology in design theory.

Most of the papers on grooming deal with a single (static) traffic matrix. Some articles consider variable (dynamic) traffic, such as finding a solution which works for the maximum traffic demand [START_REF] Berry | Reducing electronic multiplexing costs in SONET/WDM rings with dynamically changing traffic[END_REF][START_REF] Zhu | Traffic engineering in multigranularity heterogeneous optical WDM mesh networks through dynamic traffic grooming[END_REF] or for all request graphs with a given maximum degree [START_REF] Muñoz | Traffic Grooming in Unidirectional WDM Rings with Bounded Degree Request Graph[END_REF], but all keep a fixed grooming factor. In [START_REF] Colbourn | Grooming for two-period optical networks[END_REF] an interesting variation of the traffic grooming problem, grooming for two-period optical networks, has been introduced in order to capture some dynamic nature of the traffic. Informally, in the two-period grooming problem each time period supports different traffic requirements. During the first period of time there is all-to-all uniform traffic among n nodes, each request using 1/C of the bandwidth ; but during the second period there is all-to-all traffic only among a subset V of v nodes, each request now being allowed to use a larger fraction of the bandwidth, namely 1/C ′ where C ′ < C.

Denote by X the subset of n nodes. Therefore the two-period grooming problem can be expressed as follows : Two-Period Grooming in the Ring Input : Four integers n, v, C, and C ′ .

Output : A partition (denoted N(n, v; C, C ′ )) of E(K n ) into subgraphs B k , 1 ≤ k ≤ Λ, such that for all k, |E(B k )| ≤ C, and |E(B k ) ∩ (V × V)| ≤ C ′ , with V ⊆ X, |V| = v. Objective : Minimize Λ k=1 |V(B k )|.
Following [START_REF] Colbourn | Grooming for two-period optical networks[END_REF], a grooming is denoted by N(n, C). When the grooming N(n, C) is optimal, i.e. minimizes the total ADM cost, then the grooming is denoted by ON (n, C). Whether general or optimal, the drop cost of a grooming is denoted by cost N(n, C) or cost ON (n, C), respectively.

A grooming of a two-period network N(n, v; C, C ′ ) with grooming ratios (C, C ′ ) coincides with a graph decomposition (X, B) of K n (using standard design theory terminology, B is the set of all the blocks of the decomposition) such that (X, B) is a grooming N(n, C) in the first time period, and (X, B) faithfully embeds a graph decomposition of K v such that (V, D) is a grooming N(v, C ′ ) in the second time period. Let V ⊆ X. The graph decomposition (X, B) embeds the graph decomposition (V, D) if there is a mapping f : D → B such that D is a subgraph of f (D) for every D ∈ D. If f is injective (i.e., one-to-one), then (X, B) faithfully embeds (V, D). This concept of faithfully embedding has been explored in [START_REF] Colbourn | Minimum embedding of P 3 -designs into (K 4e)-designs[END_REF][START_REF] Quattrocchi | Embedding path designs in 4-cycle systems[END_REF].

We use the notation ON (n, v; C, C ′ ) to denote an optimal grooming N(n, v; C, C ′ ).

INRIA

As it turns out, an ON (n, v; C, C ′ ) does not always coincide with an ON (n, C). Generally we

have cost ON (n, v; C, C ′ ) ≥ cost ON (n, C) (see Examples 1.2 and 1.3). Of particular interest is the case when cost ON (n, v; C, C ′ ) = cost ON (n, C) (see Example 1.1). Example 1.1 Let n = 7, v = 4, C = 4. Let V = {0, 1, 2, 3} and W = {a 0 , a 1 , a 2 }.
An optimal decomposition is given by the three triangles (a 0 , 0, 1), (a 1 , 1, 2), and (a 2 , 2, 3), and the three 4-cycles (0, 2, a 0 , a 1 ), (0, 3, a 0 , a 2 ), and (1, 3, a 1 , a 2 ), giving a total cost of 21 ADMs.

This solution is valid and optimal for both C ′ = 1 and C ′ = 2, and it is optimal for the classical Traffic Grooming in the Ring problem when n = 7 and C = 4. Therefore, cost ON (7, 4; 4, 1) = cost ON (7, 4; 4, 2) = cost ON (7, 4) = 21.

Example 1.2 Let n = 7, v = 5, C = 4, and C ′ = 2. Let V = {0, 1, 2, 3, 4} and W = {a 0 , a 1 }. We see later that an optimal decomposition is given by the five kites (a 0 , 1, 2; 0), (a 0 , 3, 4; 1), (a 1 , 1, 3; 2), (a 1 , 2, 4; 0) and (a 0 , a 1 , 0; 1), plus the edge {0, 3}, giving a total cost of 22 ADMs. So cost ON (7, 5; 4, 2) = 22. Note that this decomposition is not a valid solution for C ′ = 1, since there are subgraphs containing more than one edge with both end-vertices in V.

Example 1.3 Let n = 7, v = 5, C = 4, and C ′ = 1. Let again V = {0, 1, 2, 3, 4} and W = {a 0 , a 1 }. We see later that an optimal decomposition is given by the four K 3 s (a 0 , 1, 2), (a 0 , 3, 4), (a 1 , 0, 3), and (a 1 , 2, 4), the C 4 (0, 1, a 1 , a 0 ), plus the five edges {0, 4}, {1, 3}, {0, 2}, {1, 4}, and {2, 3}, giving a total cost of 26 ADMs. So cost ON (7, 5; 4, 1) = 26. C.J. Colbourn, G. Quattrocchi and V.R. Syrotiuk [START_REF] Colbourn | Grooming for two-period optical networks[END_REF][START_REF] Colbourn | Lower bounds for graph decompositions via linear programming duality[END_REF] completely solved the cases when C = 2 and C = 3 (C ′ = 1 or 2). In this article we determine the minimum drop cost of an N(n, v; 4, C ′ ) for all n ≥ v ≥ 0 and C ′ ∈ {1, 2, 3}.

We are also interested in determining the minimum number of wavelengths, or wavecost, required in an assignment of wavelengths to a decomposition. Among the ON (n, 4)s one having the minimum wavecost is denoted by M ON (n, 4), and the corresponding minimum number of wavelengths by wavecostM ON (n, 4). We characterize the ON (n, v; C, C ′ ) whose wavecost is minimum among all ON (n, v; C, C ′ )s and denoted one by M ON (n, v; C, C ′ ) ; the wavecost is itself denoted by wavecostM ON (n, v; C, C ′ ).

We deal separately with each value of C ′ ∈ {1, 2, 3}. Table 1 summarizes the cost formulas for n = v + w > 4.

Notation and Preliminaries

We establish some graph-theoretic notation to be used throughout. We denote the edge between u and v by {u, v}. K n denotes a complete graph on n vertices and K X represents the complete graph on the vertex set X. A triangle with edges {{x, y}, {x, z}, {y, z}} is denoted by (x, y, z). A 4-cycle with edges {{x, y}, {y, z}, {z, u}, {u, x}} is denoted by (x, y, z, u). A kite with edges {{x, y}, {x, z}, {y, z}, {z, u}} is denoted by (x, y, z; u). The groomings to be produced also employ paths ; the path on k vertices P k is denoted by [x 1 , . . . , x k ] when it contains edges {x i ,

x i+1 } for 1 ≤ i < k. Now let G = (X, E) be a graph. If |X| is even, a set of |X|/2 disjoint edges in E is a 1-factor ; a partition of E into 1-factors is RR n°7101 6Jean-Claude Bermond , Charles J. Colbourn , Lucia Gionfriddo , Gaetano Quattrocchi , Ignasi Sau cost ON (v + w, v; 4, 1) =            v+w 2 if v ≤ w + 1 v+w 2 + v 2 -vw 2 if v ≥ w + 1 cost ON (v + w, v; 4, 2) =                                                                      v+w 2 if v ≤ 2w v+w 2 + 1 2 v 2 -vw 2 + δ if v > 2w and v even where δ =                1 if w = 2, or if w = 4 and v ≡ 0 (mod 4) 0 otherwise v+w 2 + 1 2 v 2 -vw -w 2 + δ if v > 2w and v odd where δ =          1 if w = 3 and v ≡ 3 (mod 4) 0 otherwise cost ON (v + w, v; 4, 3) = v+w 2 Tab. 1 -Cost formulas for n = v + w > 4.
INRIA a 1-factorization. Similarly, if |X| is odd, a set of (|X| -1)/2 disjoint edges in E is a near 1-factor ; a partition of E into near 1-factors is a near 1-factorization. We also employ well-known results on partial triple systems and group divisible designs with block size three ; see [START_REF] Colbourn | Triple systems[END_REF] for background.

The vertices of the set V are the integers modulo v denoted by 0, 1, . . . , v -1. The vertices not in V, that is in X \ V, forms the set W of size w = nv and is denoted by a 0 , . . . , a w-1 , the indices being taken modulo w.

Among graphs with three or fewer edges (i.e., when C = 3),the only graph with the minimum ratio (number of vertices over the number of edges) is the triangle. For C = 4 three different such graphs have minimum ratio 1 : the triangle, the 4-cycle, and the kite. This simplifies the problem substantially. Indeed, in contrast to the lower bounds in [START_REF] Colbourn | Lower bounds for graph decompositions via linear programming duality[END_REF], in this case the lower bounds arise from easy classification of the edges on V. We recall the complete characterization for optimal groomings with a grooming ratio of four : Theorem 2.1 [START_REF] Bermond | Traffic grooming in unidirectional WDM ring networks using design theory[END_REF][START_REF] Hu | Optimal traffic grooming for wavelength-division-multiplexing rings with all-to-all uniform traffic[END_REF] cost ON (4, 4) = 7 and, for n ≥ 5, cost ON (n, 4) = n 2 . Furthermore a M ON (4, 4) employs two wavelengths and can be realized by a kite and a P 3 (or a K 3 and a star), and a M ON (n, 4), n ≥ 5, employs n(n-1) 8 wavelengths and can be realized by t K 3 s and n(n-1)

8

t 4-cycles or kites, where

t =                0 if n ≡ 0, 1 (mod 8) 1 if n ≡ 3, 6 (mod 8) 2 if n ≡ 4, 5 (mod 8) 3 if n ≡ 2, 7 (mod 8)
.

In order to unify the treatment of the lower bounds, in a decomposition N(v + w, v; 4, C ′ ) for C ′ ∈ {1, 2}, we call an edge with both ends in V neutral if it appears in a triangle, 4-cycle, or kite ; we call it positive otherwise. An edge with one end in V and one in W is a cross edge.

Lemma 2.1

1. In an N(v + w, v; 4, C ′ ) with C ′ ∈ {1, 2}, the number of neutral edges is at most

1 2 C ′ vw. 2.
When v is odd and C ′ = 2, the number of neutral edges is at most vw -w 2 .

Proof. Every neutral edge appears in a subgraph having at least two cross edges. Thus the number of subgraphs containing one or more neutral edges is at most 1 2 vw. Each can contain at most C ′ neutral edges, and hence there are at most 1 2 C ′ vw neutral edges. This proves the first statement. Suppose now that C ′ = 2 and v is odd. Any subgraph containing two neutral edges employs exactly two cross edges incident to the same vertex in W. Thus the number α of such subgraphs is at most 1 2 w(v -1). Then remaining neutral edges must arise (if present) in triangles, kites, or 4cycles that again contain two cross edges but only one neutral edge ; their number, β, must satisfy

β ≤ vw 2 -α. Therefore the number of neutral edges, 2α+β, satisfies 2α+β ≤ 1 2 w(v-1) + vw 2 = vw-w 2 .
When C = 3 there are strong interactions among the decompositions placed on V, on W, and on the cross edges [START_REF] Colbourn | Grooming for two-period optical networks[END_REF][START_REF] Colbourn | Lower bounds for graph decompositions via linear programming duality[END_REF] ; fortunately here we shall see that the structure on V suffices to determine the lower bounds. Because every [START_REF] Bermond | Traffic grooming in unidirectional WDM ring networks using design theory[END_REF]. We use these obvious facts to establish lower and upper bounds without further comment.

N(v + w, v; 4, C ′ ) is an N(v + w, v; 4, C ′ + 1) for 1 ≤ C ′ ≤ 3, and RR n°7101 8Jean-Claude Bermond , Charles J. Colbourn , Lucia Gionfriddo , Gaetano Quattrocchi , Ignasi Sau N(v + w, v; 4, 4) coincides with N(v + w, 4), cost ON (v + w, v; 4, 1) ≥ cost ON (v + w, v; 4, 2) ≥ cost ON (v + w, v; 4, 3) ≥ cost ON (v + w,
3 Case C ′ = 1 3.1 ON (n, v; 4, 1) Theorem 3.1 Let n = v + w ≥ 5. 1. cost ON (v + w, v; 4, 1) = cost ON (v + w, 4) when v ≤ w + 1. 2. cost ON (v + w, v; 4, 1) = v+w 2 + v 2 -⌊ vw 2 ⌋ when v ≥ w + 1.
Proof. To prove the lower bound, we establish that cost ON (v + w, v; 4, 1)

≥ v+w 2 + v 2 -⌊ vw 2 ⌋.
It suffices to prove that the number of subgraphs employed in an N(v + w, v; 4, 1) other than triangles, kites, and 4-cycles is at least

⌈ v 2 -1 2 vw⌉ = v 2 -⌊ 1 2 vw⌋. By Lemma 2.
1, this is a lower bound on the number of positive edges in any such decomposition ; because each positive edge lies in a different subgraph of the decomposition, the lower bound follows. Now we turn to the upper bounds. For the first statement, because an ON (v + w, v; 4, 1) is also an ON (v + w, v -1; 4, 1), it suffices to consider v ∈ {w, w + 1}. When v = w, write v = 4s + t with t ∈ {0, 3, 5, 6}. Form on V a complete multipartite graph with s classes of size four and one class of size t. Replace edge e = {x, y} of this graph by the 4-cycle (x, y, a x , a y ). On {x 1 , . . . , x ℓ , a x 1 , . . . , a x ℓ } whenever {x 1 , . . . , x ℓ } forms a class of the multipartite graph, place a decomposition that is optimal for drop cost and uses 4, 7, 12, and 17 wavelengths when ℓ is 3, 4, 5, or 6, respectively (see Appendix A).

Now let v = w + 1. Let V = {0, . . . , v -1} and W = {a 0 , . . . , a v-2 }. Form triangles (i, i + 1, a i ) for 0 ≤ i < v -1. Then form 4-cycles (i, j + 1, a i , a j ) for 0 ≤ i < j ≤ v -2.
Finally, suppose that v ≥ w + 2. When v is even, form a 1-factorization F 0 , . . . , F v-2 on V. For 0 ≤ i < w, let {e i j : 1 ≤ j ≤ v 2 } be the edges of F i , and form triangles T i j = {a i } ∪ e i j . Now for 0 ≤ i < w ; 1 ≤ j ≤ ⌊ w 2 ⌋ ; and furthermore j w 2 if i ≥ w 2 and w is even, adjoin edge {a i , a i+ j mod w } to T i j to form a kite. All edges of 1-factors

{F i : w ≤ i < v -1} are taken as K 2 s. When v is odd, form a near 1-factorization F 0 , . . . , F v-1 on V, in which F v-1 contains the edges {{2h, 2h + 1} : 0 ≤ h < v-1
2 }, and near 1-factor

F i misses vertex i for 0 ≤ i < v. Then form 4-cycles (2h, 2h + 1, a 2h+1 , a 2h ) for 0 ≤ h < ⌊ w 2 ⌋. For 0 ≤ i < w, let {e i j : 1 ≤ j ≤ v-1
2 } be the edges of F i , and form triangles T i j = {a i } ∪ e i j . Without loss of generality we assume that w -1 ∈ e 01 ; when w is odd, adjoin {w -1, a w-1 } to T 01 to form a kite. Now for 0 ≤ i < w ; 1 ≤ j ≤ ⌊ w 2 ⌋ ; and furthermore j w 2 if i ≥ w 2 and w is even and j

1 if i = 2h for 0 ≤ h < ⌊ w 2 ⌋, adjoin edge {a i , a i+ j mod w } to T i j to form a kite. All edges of near 1-factors {F i : w ≤ i < v -1} and the v-1 2 -⌊ w 2 ⌋ remaining edges of F v-1 are taken as K 2 s.
When v ≥ w + 1, each subgraph contains exactly one edge on V and so their number is v 2 . This fact is later used to prove Theorem 3.3. Proof. We need only treat the cases when v ∈ {w, w -1} ; the case with v = w is handled in the proof of Theorem 3.1. When v = w -1, the argument is identical to that proof, except that we choose v = 4s + t with t ∈ {0, 1, 2, 3} and place decompositions on {x 1 , . . . , x ℓ , a x 1 , . . . , a x ℓ , a v } instead, with 1,3,6,9 wavelengths when ℓ = 1, 2, 3, 4 respectively (see Appendix B).

Theorem 3.3 When v > w, wavecost M ON (v + w, v; 4, 1) = v 2 .
Proof. Since every edge on V appears on a different wavelength, v 2 is a lower bound. As noted in the proof of Theorem 3.1 the constructions given there meet this bound.

The solutions used from Theorem 3.1 are (essentially) the only ones to minimize the number of graphs in an ON (v+w, v; 4, 1) with v > w. However, perhaps surprisingly they are not the only ones to minimize the number of wavelengths. To see this, consider a ON (v + w, v; 4, 1) with v > w > 2 from Theorem 3.1. Remove edges {a 0 , a 1 }, {a 0 , a 2 }, and {a 1 , a 2 } from their kites, and form a triangle from them. This does not change the drop cost, so the result is also an ON (v + w, v; 4, 1). It has one more graph than the original. Despite this, it does not need an additional wavelength, since the triangle (a 0 , a 1 , a 2 ) can share a wavelength with an edge on V. In this case, while minimizing the number of connected graphs serves to minimize the number of wavelengths, it is not the only way to do so.

4 Case C ′ = 2 4.1 ON (n, v; 4, 2)
Theorem 4.1 Let v + w ≥ 5 and v be even. As in the proof of Lemma 2.1, denote by α (resp. β) the number of subgraphs containing 2 (resp 1) neutral edges and so at least two cross edges. We have 2α + β ≤ 2α + 2β ≤ vw. Equality in the lower bound, when v ≡ 0 (mod 4), arises only when β = 0 and therefore to meet the bound an ON (w, 4) must be placed on W implying that δ = 1 if w = 2 or 4. When v ≡ 2 (mod 4), we can have 2α + β = vw -1 and so β = 1. We can use an edge on W in a graph with an edge on V. But when w = 4, the five edges that would remain on W require drop cost 6, and so δ = 1. Now we turn to the upper bounds. If w ≥ v -1, apply Theorem 3.1. Suppose that w ≤ v -2. Let V = {0, . . . , 2t -1} and W = {a 0 , . . . , a w-1 }. Place an ON (w, 4) on W. Form a 1-factorization on V containing factors {F 0 , . . . , F w-1 , G 0 , . . . , G 2t-2-w } in which the last two 1-factors are {{2h, 2h + 1} : 0 ≤ h < t} and {{2h + 1, 2h + 2 mod 2t} : 0 ≤ h < t}, whose union is a Hamilton cycle. For 0 ≤ i < w, form triangles T i j by adding a i to each edge e i j ∈ F i . For 0 ≤ i < min(w, 2t -1w), observe that H i = F i ∪ G i is a 2-factor containing even cycles. Hence there is a bijection σ mapping edges of F i to edges of G i so that e and σ(e) share a vertex. Adjoin edge σ(e i j ) to the triangle T i j to form a kite. In this way, all edges between V and W appear in triangles or kites, and all edges on V are employed when v ≤ 2w. When v ≥ 2w + 2, the edges remaining on V are those of the factors G w , . . . , G v-2-w .

1. When v ≤ 2w, cost ON (v + w, v; 4, 2) = cost ON (v + w, 4). 2. When v ≥ 2w + 2, cost ON (v + w, v; 4, 2) = v+w 2 + ⌈ 1 2 v 2 ⌉ -vw 2 + δ,
When v 2w + 2, the union of these edges is connected because the union of the last two is connected, and hence it can be partitioned into P 3 s (and one P 2 when v ≡ 2 (mod 4)) [START_REF] Caro | Decompositions of trees into isomorphic subtrees[END_REF][START_REF] Yavorskii | Representations of directed graphs and ψ-transformations[END_REF]. When w = 2 and v ≡ 2 (mod 4), the drop cost can be reduced by 1 as follows. Let {x, y} be the P 2 in the decomposition, and let {x, z} ∈ G 0 . Let T be the triangle obtained by removing {x, z} from its kite. Add {a 0 , a 1 } to T to form a kite. Add the P 3 [y, x, z]. In this way two isolated P 2 s are replaced by a P 3 , lowering the drop cost by 1.

When v = 2w + 2, we use a variant of this construction. Let R be a graph with vertex set V that is isomorphic to v 4 K 4 s when v ≡ 0 (mod 4) and to v-6 4 K 4 s and one K 3,3 when v ≡ 2 (mod 4). Let F 1 , . . . , F w-1 , G 1 , . . . , G w-1 be the 1-factors of a 1-factorization of the complement of R (one always exists [START_REF] Rosa | Premature sets of 1-factors, or, how not to schedule round-robin tournaments[END_REF]). Proceed as above to form kites using a i for 1 ≤ i < w and the edges of F i and G i . For each K 4 of R with vertices {p, q, r, s}, form kites (a 0 , q, p; r) and (a 0 , r, s; p). Then add the P 3 [r, q, s]. If R contains a K 3,3 with bipartition {{p, q, r}, {s, t, u}}, add kites (a 0 , s, p; t), (a 0 , q, t; r), and (a 0 , r, u; p). What remains is the P 4 [r, s; q, u], which can be partitioned into a P 2 and a P 3 .

In order to treat the odd case, we establish an easy preliminary result : Lemma 4.1 Let w > 3 be a positive integer. The graph on w vertices containing all edges except for ⌊ w 2 ⌋ disjoint edges (i.e., K w \ ⌊ w 2 ⌋K 2 ) can be partitioned into 1. 4-cycles when w is even ; 2. kites and 4-cycles when w ≡ 1 (mod 4) ; and

kites, 4-cycles, and exactly two triangles when w ≡ 3 (mod 4).

Proof. Let W = {a 0 , . . . , a w-1 }. When w is even, form 4-cycles {(a 2i , a 2 j , a 2i+1 , a 2 j+1 ) : 0 ≤ i < j < w 2 } leaving uncovered the w 2 edges {a 2i , a 2i+1 }. (This is also a consequence of a much more general result in [START_REF] Fu | Forest leaves and 4-cycles[END_REF].)

When w is odd, the proof is by induction on w by adding four new vertices. So we provide two base cases for the induction to cover all odd values of w.

INRIA

For w = 5, K 5 \ {{a 0 , a 1 }, {a 2 , a 3 }} can be partitioned into the two kites (a 2 , a 4 , a 0 ; a 3 ) and (a 3 , a 4 , a 1 ; a 2 ).

For w = 7, K 7 \{{a 0 , a 1 }, {a 2 , a 3 }, {a 4 , a 5 }} can be partitioned into the kites (a 3 , a 6 , a 0 ; a 5 ), (a 1 , a 6 , a 4 ; a 3 ) and (a 5 , a 6 , a 2 ; a 1 ), and the K 3 s (a 0 , a 2 , a 4 ) and (a 1 , a 3 , a 5 ).

By induction consider an optimal decomposition of K w -F, with F = {{a 2h , a 2h+1 } : 0 ≤ h < w-1 2 }. Add four vertices a w , a w+1 , a w+2 , a w+3 . Add the C 4 s (a 2h , a w , a 2h+1 , a w+1 ) and (a 2h , a w+2 , a 2h+1 , a w+3 ) where 0 ≤ h < w-1 2 . Cover the edges of the K 5 on {a w-1 , a w , a w+1 , a w+2 , a w+3 } minus the edges {a w-1 , a w } and {a w+1 , a w+2 }, using two kites as shown for the case when w = 5. Theorem 4.2 Let v + w ≥ 5 and v be odd.

1. When v ≤ 2w -1, cost ON (v + w, v; 4, 2) = cost ON (v + w, 4). 2. When v ≥ 2w + 1, cost ON (v + w, v; 4, 2) = v+w 2 + ⌈ 1 2 v 2 -vw + ⌈ w 2 ⌉ ⌉ + δ
, where δ = 1 if w = 3 and v ≡ 3 (mod 4), 0 otherwise. Proof. To prove the lower bound, it suffices to prove that the number of subgraphs employed in an N(v + w, v; 4, 2) other than triangles, kites, and 4-cycles is at least

⌈ 1 2 v 2 -vw + ⌈ w 2 ⌉ ⌉.
As in the proof of Theorem 4.1, this follows from Lemma 2.1. When w = 3 and v ≡ 3 (mod 4), at least v 2 -3v + 2 edges are positive, an even number. To meet the bound, exactly one cross edge remains and exactly two edges on W remain. These necessitate a further graph that is not a triangle, kite, or 4-cycle. Now we turn to the upper bounds. By Theorem 4.1, cost ON ((v + 1)

+ (w -1), v + 1; 4, 2) = cost ON (v + w, 4) when v ≤ 2w -3. So suppose that v ≥ 2w -1. Write v = 2t + 1.
When w = t + 1, form a near 1-factorization on V consisting of 2t + 1 near 1-factors, F 0 , . . . , F t , G 0 , . . . , G t-1 . Without loss of generality, F i misses vertex i for 0 ≤ i ≤ t, and F t contains the edges {{k, t + k + 1} : 0 ≤ k < t}. The union of any two near 1-factors contains a nonnegative number of even cycles and a path with an even number of edges. For 0 ≤ i ≤ t, form triangles T i j by adding a i to each edge e i j ∈ F i . As in the proof of Theorem 4.1, for 0 ≤ i < t, use the edges of G i to convert every triangle T i j into a kite. Then add edge {i, a i } to triangle T ti constructed from edge {i, t + 1 + i}. What remains is the single edge {t, a t } together with all edges on W.

When w {2, 4}, place an ON (w, 4) on W of cost w 2 so that a t appears in a triangle in the decomposition, and use the edge {t, a t } to convert this to a kite. We use a decomposition having 1 ≤ δ ≤ 4 triangles, therefore getting a solution with at most 3 triangles. Such a decomposition exists by Theorem 2.1 if w 0, 1 (mod 8). If w ≡ 0, 1 (mod 8) we build a solution using 4 triangles as follows. If w ≡ 1 (mod 8), form an ON (w -2, 4) on vertices {0, . . . , w -3} with 3 triangles. Add the triangle (w -3, w -2, w -1) and the 4-cycles {(2h, w -2, 2h + 1, w -1) : 0 ≤ h < w-3 2 }. For w = 8 a solution with 4 triangles is given in Appendix C. In general, for w ≡ 0 (mod 8), form an ON (w-8, 4) on vertices {0, . . . , w-9} with 4 triangles. Add the 4-cycles {(2h, w-2 j, 2h+1, w-2 j+ 1) : 0 ≤ h < w- 8 2 }; 1 ≤ j ≤ 4 and an ON (8, 4) without triangles on the 8 vertices {w -8, . . . , w -1}. Two values for w remain. When w = 2, an ON (5, 3; 4, 1) is also an ON (5, 3; 4, 2). The case when v = 7 and w = 4 is given in Appendix C. The solution given has only 1 triangle.

Henceforth w ≤ t. For t > 2, form a near 1-factorization {F 0 , . . . ,

F w-1 , G 0 , . . . , G 2t-1-w } of K v \ C t ,
where C t is the t-cycle on (0, 1, . . . , t -1) ; such a factorization exists [START_REF] Plantholt | The chromatic index of graphs with a spanning star[END_REF]. Name the factors RR n°7101 12Jean-Claude Bermond , Charles J. Colbourn , Lucia Gionfriddo , Gaetano Quattrocchi , Ignasi Sau so that the missing vertex in F i is ⌊i/2⌋ for 0 ≤ i < w (this can be done, as every vertex i satisfying 0 ≤ i < t is the missing vertex in two of the near 1-factors). Form triangles using F 0 , . . . , F w-1 and convert to kites using G 0 , . . . , G w-1 as before. There remain 2(tw) near 1-factors G w , . . . , G 2t-1-w . For 0 ≤ h < tw, G w+2h ∪ G w+2h+1 contains even cycles and an even path, and so partitions into P 3 s. Then the edges remaining are (1) the edges of the t-cycle ; (2) the edges {{⌊i/2⌋, a i } : 0 ≤ i < w} ; and

(3) all edges on W. For 0 ≤ i < ⌊ w 2 ⌋, form triangle (i, a 2i , a 2i+1 ) and add edge {i, i + 1} to convert it to a kite. Edges {{i, i + 1 mod t} : ⌊ w 2 ⌋ ≤ i < t} of the cycle remain from (1) ; edge { w-1 2 , a w-1 } remains when w is odd, and no edge remains when w is even, from (2) ; and all edges excepting a set of ⌊ w 2 ⌋ disjoint edges on W remain.

When w 3, we partition the remaining edges in (1) (which form a path of length t -⌊ w 2 ⌋), into P 3 s when t -⌊ w 2 ⌋ is even, and into P 3 s and the P 2 {0, t -1} when t -⌊ w 2 ⌋ is odd. We adjoin edge { w-1 2 , a w-1 } to the P 3 (from the t-cycle) containing the vertex w-1 2 to form a P 4 . Finally, we apply Lemma 4.1 to exhaust the remaining edges on W.

When w = 3, the remaining edges are those of the path [0, t -1, t -2, . . . , 2, 1, a 2 ] and edges {{a 2 , a 0 }, {a 2 , a 1 }}. Include {{1, 2}, {1, a 2 }, {a 2 , a 0 }, {a 2 , a 1 }} in the decomposition, and partition the remainder into P 3 s and, when v ≡ 3 (mod 4), one P 2 {0, t -1}.

The case when t = 2 is done in Example 1.2 (the construction is exactly that given above, except that we start with a near 1-factorization of K 5 \ {{0, 1}, {0, 3}}).

M ON

(n, v; 4, 2) Theorem 4.3 For C ′ = 2 and v ≤ 2w, wavecost M ON (v + w, v; 4, 2) = wavecost M ON (v + w, 4).
Proof. It suffices to prove the statement for v ∈ {2w -2, 2w -1, 2w}. When v = 2w -1, apply the construction given in the proof of Theorem 4.2, where we noted that there are at most 3 triangles. The proof of Theorem 4.2 provides explicit solutions when w ∈ {2, 4}. Now suppose that v = 2w. In the proof of Theorem 4.1, v 2 = w triangles containing one edge on V and two edges between a vertex of V and a w-1 remain. Then convert w -1 triangles to kites using edges on W incident to a w-1 . That leaves one triangle. When the remaining edges on the w -1 vertices of W support a M ON (w -1, 4) that contains at most two triangles, we are done. It remains to treat the cases when w -1 ≡ 2, 7 (mod 8) or w -1 = 4.For the first case, let x be one vertex of the triangle left containing a w-1 , namely (a w-1 , x, y). Consider the pendant edge {x, t} ∈ G w-2 used in a kite containing a w-2 . Delete {x, t} from this kite and adjoin {a w-3 , a w-2 } to the unique triangle so formed forming another kite. Finally adjoin {x, t} to the triangle (a w-1 , x, y). Proceed as before, but partition all edges on {a 0 , . . . , a w-2 } except edge {a w-3 , a w-2 } into 4-cycles and kites. The case when w -1 = 4 is similar, but we leave three of the triangles arising from F w-1 and partition K 5 \ P 3 into two kites. Now suppose that v = 2w -2. We do a construction similar to that above. In the proof of Theorem 4.1, there remain 3 v 2 = 3(w -1) triangles joining a w-3 (resp. a w-2 , a w-1 ) to F w-3 (resp. F w-2 , F w-1 ). Then convert the w -1 triangles containing a w-1 to kites using edges on W incident INRIA to a w-1 , w -2 triangles containing a w-2 to kites using the remaining edges on W incident to a w-2 , and w -3 triangles containing a w-3 to kites using edges on W incident to a w-3 . That leaves three triangles. So, if w -3 ≡ 0, 1 (mod 8) we are done. Otherwise, as above, choose in each of the three remaining triangles vertices x 1 , x 2 , x 3 ; consider the edges {x 1 , t 1 } (resp. {x 2 , t 2 }) appearing in the kites containing a w-4 and x 1 (resp. a w-4 and x 2 ), and the edge {x 3 , t 3 } in the kite containing a w-5 and x 3 . Delete these edges and adjoin them to the three remaining triangles. Finally adjoin the edges {a w-4 , a w-5 } and {a w-4 , a w-6 } to the two triangles obtained from the two kites containing a w-4 , and adjoin the edge {a w-5 , a w-6 } to the triangle obtained from the kite containing a w-5 . Proceed as before, but partition all edges on {a 0 , . . . , a w-4 } except the triangle (a w-6 , a w-5 , a w-4 ) into 4-cycles and kites.

Theorem 4.4 1. When v > 2w is even, wavecost M ON (v + w, v; 4, 2) = 2 v 2 + w 2 /4 . 2. When v > 2w is odd, wavecost M ON (v + w, v; 4, 2) = 2 v 2 + (w -1)(w + 1) 2 /4 .
Proof. First we treat the case when v is even. Then (by Theorem 4.1) an ON (v + w, v; 4, 2) must employ vw or vw -1 neutral edges, using all vw edges between V and W. Each such graph uses two edges on V and none on W, except that a single graph may use one on V and one on W. Now the edges of V must appear on ⌈ 1 2 v 2 ⌉ different wavelengths, and these wavelengths use at most one edge on W (when v ≡ 2 (mod 4)). Thus at least ⌈ w 2 /4⌉ additional wavelengths are needed when v ≡ 0 (mod 4), for a total of ⌈ v 2 /2 + w 2 /4⌉. When v ≡ 2 (mod 4), at least ⌈( w 2 -1)/4⌉ additional wavelengths are needed ; again the total is ⌈ v 2 /2 + w 2 /4⌉. Theorem 4.1 realizes this bound. When v is odd, first suppose that w is even. In order to realize the bound of Theorem 4.2 for drop cost, by Lemma 2.1, w 2 neutral edges appear in subgraphs with one neutral edge and all other neutral edges appear in subgraphs with two. In both cases, two edges between V and W are consumed by such a subgraph. When two neutral edges are used, no edge on W can be used ; when one neutral edge is used, one edge on W can also be used. It follows that the number of wavelengths is at least

1 2 ( v 2 -w 2 ) + w 2 + 1 4 ( w 2 -w 2 )
. This establishes the lower bound. The case when w is odd is similar. The proof of Theorem 4.2 gives constructions with at most 3 triangles and so establishes the upper bound except when v ≡ 1 (mod 4) and w ≡ 3 (mod 4), w 3, where the construction employs one more graph than the number of wavelengths permitted. However, one graph included is the P 2 {0, t -1}, and in the decomposition on W, there is a triangle. These can be placed on the same wavelength to realize the bound.

When v ≡ 1 (mod 4) and w ≡ 3 (mod 4), w 3, we place a disconnected graph, P 2 ∪ K 3 , on one wavelength in order to meet the bound. The construction of Theorem 4.2 could be modified to RR n°7101 14Jean-Claude Bermond , Charles J. Colbourn , Lucia Gionfriddo , Gaetano Quattrocchi , Ignasi Sau avoid this by instead using a decomposition of K w \ (K 3 ∪ w-3 2 K 2 ) into 4-cycles and kites, and using the strategy used in the case for w = 3. In this way, one could prove the slightly stronger result that the number of (connected) subgraphs in the decomposition matches the lower bound on number of wavelengths needed.

In Theorem 3.3, the number of wavelengths and the drop cost are minimized simultaneously by the constructions given ; each constructed ON (v+w, v; 4, 1) has not only the minimum drop cost but also the minimum number of wavelengths over all N(v + w, v; 4, 1)s. This is not the case in Theorem 4.4. For example, when v > (1 + √ 2)w, it is easy to construct an N(v + w, v; 4, 2) that employs only ⌈ v 2 /2⌉ wavelengths, which is often much less than are used in Theorem 4.4. We emphasize therefore that a M ON (v + w, v; 4, 2) minimizes the number of wavelengths over all ON (v + w, v; 4, 2)s, not necessarily over all N(v + w, v; 4, 2)s.

When w

≥ 1, cost ON (v + w, v; 4, 3) = cost ON (v + w, 4). 2. cost ON (v + 0, v; 4, 3) = cost ON (v, 3).
Proof. The second statement is trivial. Moreover cost ON (n, 4) = cost ON (n, 3) when n ≡ 1, 3 (mod 6), and hence the first statement holds when v + w ≡ 1, 3 (mod 6). To complete the proof it suffices to treat the upper bound when w = 1.

When v + 1 ≡ 5 (mod 6), there is a maximal partial triple system (X, B) with |X| = v + 1 covering all edges except those in the 4-cycle (r, x, y, z). Set W = {r}, V = X \ W, and add the 4-cycle to the decomposition to obtain an ON (v + 1, v; 4, 3).

When v ≡ 1, 5 (mod 6), set ℓ = v -1 and when v ≡ 3 (mod 6) set ℓ = v -3. Then ℓ is even. Form a maximal partial triple system (V, B), |V| = v, covering all edges except those in an ℓ-cycle (0, 1, . . . , ℓ -1) [START_REF] Colbourn | Quadratic leaves of maximal partial triple systems[END_REF]. Add a vertex a 0 and form kites (a 0 , 2i, 2i + 1; (2i + 2) mod ℓ) for 0 ≤ i < ℓ 2 . For i ∈ {ℓ, . . . , v -1}, choose a triple B i ∈ B so that i ∈ B i and B i = B j only if i = j. Add {a 0 , i} to B i to form a kite. This yields an ON (v + 1, v; 4, 3).

M ON (n, v; 4, 3)

We focus first on lower bounds in Section 5.2.1 and then we provide constructions attaining these lower bounds in Section 5.2.2.

Lower Bounds

When C ′ = 3, Theorem 5.1 makes no attempt to minimize the number of wavelengths. We focus on this case here. Except when n ∈ {2, 4} or v = n, cost ON (n, v; 4, 3) = n 2 , and every graph in an INRIA ON (n, v; 4, 3) is a triangle, kite, or 4-cycle. Let δ, κ, and γ denote the numbers of triangles, kites, and 4-cycles in the grooming, respectively. Then 3δ + 4κ + 4γ = n 2 , and the number of wavelengths is δ + κ + γ. Thus in order to minimize the number of wavelengths, we must minimize the number δ of triangles. We focus on this equivalent problem henceforth.

In an ON (n, v; 4, 3), for 0 ≤ i ≤ 3 and 0 ≤ j ≤ 4, let δ i j , κ i j , and γ i j denote the number of triangles, kites, and 4-cycles, respectively, each having i edges on V and j edges between V and W. The only counts that can be nonzero are δ 00 , δ 02 , δ 12 , δ 30 ; κ 00 , κ 01 , κ 02 , κ 03 , κ 12 , κ 13 , κ 22 , κ 31 ; γ 00 , γ 02 , γ 04 , γ 12 , γ 22 . We write σ i j = κ i j + γ i j when we do not need to distinguish kites and 4-cycles. Our objective is to minimize δ 00 + δ 02 + δ 12 + δ 30 subject to certain constraints ; we adopt the strategy of [START_REF] Colbourn | Lower bounds for graph decompositions via linear programming duality[END_REF] and treat this as a linear program.

Let ε = 0 when v ≡ 1, 3 (mod 6), ε = 2 when v ≡ 5 (mod 6), and ε = v 2 when v ≡ 0 (mod 2). We specify the linear program in Figure 1. The first row lists the primal variables. The second lists coefficients of the objective function to be minimized. The remainder list the coefficients of linear inequalities, with the final column providing the lower bound on the linear combination specified. The first inequality states that the number of edges on V used is at least the total number on V, while the second specifies that the number of edges used between V and W is at most the total number between V and W. For the third, when v ≡ 5 (mod 6) at least four edges on V are not in triangles, and so at least two graphs containing edges of V do not have a triangle on V ; when v ≡ 0 (mod 2) every graph can induce at most two odd degree vertices on V, yet all are odd in the decomposition. We do not solve this linear program. Rather we derive lower bounds by considering its dual. Let y 1 , y 2 , and y 3 be the dual variables. A dual feasible solution has y 1 = 1 3 , y 2 = 1, and y 3 = 4 3 , yielding a dual objective function value of 1 6 v(v -1)vw + 4 3 ε. Recall that every dual feasible solution gives a lower bound on all primal feasible solutions On the other hand, 3δ ≡ n 2 (mod 4) and so δ ≡ 9δ ≡ 3 n 2 (mod 4). The value of 3 n 2 (mod 4) is in fact the value of t given in Theorem 2.1. Therefore if x is a lower bound on δ in an ON (n, v; 4, 3), so is x n , where x n denotes the smallest nonnegative integer x such that x ≥ x and x ≡ 3 n 2 (mod 4).

δ 30 δ 12 δ 02 δ 00 κ 31 σ 22 κ 13 σ 12 γ 04 κ 03 σ 02 κ 01 σ 00 1 1 1 1 0 0 0 0 0 0 0 0 0 3 1 0 0 3 2 1 1 0 0 0 0 0 v 2 0 -2 -2 0 -1 -2 -3 -2 -4 -3 -2 -1 0 -vw 0 1 0 0 0 1 1 1 0 0 0 0 0 ε
The discussion above proves the general lower bound on the number of triangles :

Theorem 5.2 Let v + w ≥ 5, and let the two triangles in the M ON (3 + 2, 2; 4, 3) to kites using these. What remains is all edges on {a 0 , . . . , a w-3 } and everything is in kites or 4-cycles excepting one triangle involving a 0 and one involving a 1 . If w -2 ≡ 0, 1, 3, 6 (mod 8), place a M ON (w -2, 4) on {a 0 , . . . , a w-3 }. Otherwise partition all edges on {a 0 , . . . , a w-3 } except {a 0 , a 2 } and {a 1 , a 2 } into kites, 4-cycles, and at most one triangle, and use the last two edges to form kites with the excess triangles involving a 0 and a 1 . The partition needed is easily produced for w -2 ∈ {4, 5, 7, 9} and hence by induction for all the required orders.

Case E1. v ≡ 0 (mod 2) and w ≤ v+2 6 . Write v = 6t + s for s ∈ {0, 2, 4}. Let L = (V, E) be a graph with edges {{3i, 3i + 1}, {3i, 3i + 2}, {3i + 1, 3i + 2} : 0 ≤ i < t} ∪ {{i, 3t + i} : 0 ≤ i < 3t}, together with {6t, 6t + 1} when s = 2 and with {{6t, 6t + 1}, {6t, 6t + 2}, {6t, 6t + 3}} when s = 4. Let (V, B) be a partial triple system covering all edges except those in L (this is easily produced). Let D i = {0, . . . , w -2} for 0 ≤ i < v. Apply the general prescription. For 0 ≤ i < t and j ∈ {0, 1, 2}, form the 4-cycle (a w-1 , 3i + (( j + 1) mod 3), 3i + j, 3t + 3i + j). When s = 4, form 4-cycle (a w-1 , 6t + 2, 6t, 6t + 3). When s ∈ {2, 4}, form a triangle (a w-1 , 6t, 6t + 1). All edges on V are used and all edges on W remain. All edges between V and W are used. Except when w ∈ {2, 4}, or w ≡ 2, 7 (mod 8) and v ≡ 2, 4 (mod 6) form a M ON (w, 4) on W to complete the proof. When w ≡ 2, 7 (mod 8) and v ≡ 2, 4 (mod 6), convert {a w-1 , 6t, 6t + 1} to a kite using an edge of the K w , and partition the K w \ K 2 into kites and 4-cycles. When w ∈ {2, 4}, remove edges {a 0 , 0} and {a 1 , 0} from their kites, and partition K w together with these edges. Case E2. v ≡ 2 (mod 6) and w = v+4 6 . Choose m as large as possible so that m ≤ v 2 , m ≤ w 2 , and w 2m ≡ 0 (mod 4). Partition the w 2 edges on W into sets E c and E o with |E c | = m, so that the edges on E o can be partitioned into kites and 4-cycles ; this is easily done. Place these kites and 4-cycles on W. Then let {e i : 0 ≤ i < m} be the edges in E c ; let a f i ∈ e i when 0 ≤ i < m ; f i = 0 when m ≤ i < v-2 2 ; and f (v-2)/2 = 1 if m < v 2 . Next form a 3-GDD of type 2 v/2 on V so that {{2i, 2i + 1} : 0 ≤ i < v 2 } forms the groups, and B forms the blocks. For 0 ≤ i < v 2 , let D 2i = D 2i+1 = {0, . . . , w -1} \ { f i }. Apply the general prescription. Now for 0 ≤ i < v 2 , form the triangle (a f i , 2i, 2i + 1) and for 0 ≤ i < m add edge e i to form a kite. At most three triangles remain except when v ∈ {14, 20}, where four triangles remain. To treat these cases, we reduce the number of triangles ; without loss of generality, the 3-GDD contains a triple {v -8, v -6, v -4} in a kite with edge {a 1 , v -8}. Remove this kite, and form kites (a 0 , v -7, v -8; v -6), (a 0 , v -5, v -6; v -4), (a 0 , v -3, v -4; v -8), and (v -2, v -1, a 1 ; v -8).

Conclusions

The determination of cost ON (n, v; C, C ′ ) appears to be easier when C ′ = 4 than the case for C ′ = 3 settled in [START_REF] Colbourn | Grooming for two-period optical networks[END_REF][START_REF] Colbourn | Lower bounds for graph decompositions via linear programming duality[END_REF]. Nevertheless the very flexibility in choosing kites, 4-cycles, or triangles also results in a wide range of numbers of wavelengths among decompositions with optimal drop cost. This leads naturally to the question of minimizing the drop cost and the number of wavelengths simultaneously. In many cases, the minima for both can be realized by a single decomposition. However, it may happen that the two minimization criteria compete. Therefore we have determined the minimum number of wavelengths among all decompositions of lowest drop cost for the specified values of n, v, and C ′ .

INRIA 3 . 2 MTheorem 3 . 2

 3232 ON (n, v;[START_REF] Bermond | Traffic grooming in unidirectional WDM ring networks using design theory[END_REF][START_REF] Bermond | Minimizing SONET ADMs in unidirectional WDM rings with grooming ratio 3[END_REF] Let v + w ≥ 5. For C ′ = 1 and v ≤ w, wavecost M ON (v + w, v; 4, 1) = wavecost M ON (v + w, 4).

where δ = 1 2 v 2 -

 122 if w = 4 or if w = 2 and v ≡ 0 (mod 4), and δ = 0 otherwise.Proof. By Lemma 2.1, v2vw is a lower bound on the number of positive edges in any N(v + w, v; 4, 2) ; every subgraph of the decomposition containing a positive edge contains at most two positive edges. So the number of subgraphs employed in an N(v + w, v; 4, 2) other than triangles, kites, and 4-cycles is at least ⌈ 1 vw ⌉. The lower bound follows for w 2, 4.RR n°710110Jean-Claude Bermond , Charles J.Colbourn , Lucia Gionfriddo , Gaetano Quattrocchi , Ignasi Sau

5 Case C ′ = 3 5. 1 Theorem 5 . 1

 3151 ON (n, v; 4, 3) Let v + w ≥ 5.

Fig. 1 -

 1 Fig. 1 -The linear program for ON (n, v; 4, 3).

  Corollary 5.5 Let v ≥ 4 and µ 3 (v) be defined by : v 6 6t, t ≥ 2 1 + 6t 2 + 6t 9 3 + 6t, t ≥ 2 4 10 4 + 6t, t ≥ 2 5 + 6t

	µ 3 (v) 1	1 + t	t	1 + t 1	1 + t	1 2	2 + t	1 + t
	Then wavecost M ON (v + w, v; 4, 3) = (v+w)(v+w-1) 8	if and only if w ≥ µ 3 (v).

INRIA

RR n°7101

Acknowledgments

Research of the authors is supported by MIUR-Italy (LG,GQ), European project IST FET AEO-LUS, PACA region of France, Ministerio de Educación y Ciencia of Spain, European Regional Development Fund under project TEC2005-03575, Catalan Research Council under project 2005SGR00256, and COST action 293 GRAAL, and has been partially done in the context of the crc Corso with France Telecom.

Then the number of triangles in an ON (v + w, v; 4, 3) is at least

Remark 5. [START_REF] Bermond | Grooming in unidirectional rings : K 4e designs[END_REF] In particular, if v is odd and w ≥ ⌈ v-1 6 ⌉ or if v is even and w ≥ ⌈ v-4 6 ⌉, then L(v, w) ≤ 0 and the minimum number of triangles is δ min (v, w) = 0 v+w ≤ 3.

Upper Bounds

We first state two simple lemmas to be used intensively in the proof of Theorem 5.4. The following result shows that in fact we do not need to check exactly that the number of triangles of an optimal construction meets the bound of Theorem 5.2. Lemma 5.1 Any ON (v + w, v; 4, 3) is a M ON (v + w, v; 4, 3) if the number of triangles that it contains is at most max(3, ⌈L(v, w)⌉ + 3).

Proof. In the closed interval [⌈L(v, w)⌉, ⌈L(v, w)⌉ + 3] there is exactly one integer congruent to 3 n 2 (mod 4), and so necessarily exactly one integer equal to δ min (v, w).

Combining Remark 5.3 and Lemma 5.1 we deduce that when v is odd and w ≥ ⌈ v- 1 6 ⌉ or if v is even and w ≥ ⌈ v- 4 6 ⌉, to prove the optimality of a construction it is enough to check that there are at most three triangles.

As a prelude to the constructions, let (V, B) be a partial triple system, V = {0, . . . , v -1}, and B = {B 1 , . . . , B b }. Let r i be the number of blocks of B that contain i ∈ V. A headset is a multiset S = {s 1 , . . . , s b } so that s k ∈ B k for 1 ≤ k ≤ b, and for 0

Lemma 5.2 Every partial triple system has a headset.

Proof. Form a bipartite graph Γ with vertex set V ∪ B, and an edge {v, B} for v ∈ V and B ∈ B if and only if v ∈ B. The graph Γ admits an equitable 3-edge-colouring [START_REF] De Werra | Equitable colorations of graphs[END_REF] ; that is, the edges can be coloured green, white, and red so that every vertex of degree d is incident with either ⌊d/3⌋ or ⌈d/3⌉ edges of each colour. Then for 1 ≤ k ≤ b, B k is incident to exactly three edges, and hence to exactly one edge {i k , B k } that is green ; set s k = i k . Then (s 1 , . . . , s b ) forms the headset.

INRIA

Proof. The lower bound follows from Theorem 5.2, so we focus on the upper bound. When w ≥ 1, an ON (v + w, v; 4, 3) of cost v+w 2 is an ON (v + w, v -1; 4, 3). Let us show that it suffices to prove the statement for w ≤ v+9 6 when v is odd, and for w ≤ v+4 6 when v is even. Equivalently, we show that if it is true for these values of w, then it follows for any w. Note that

Indeed, let v be even. If w = ⌊ v+4 6 ⌋ + 1, the result follows from the case for v + 1 (odd) and

6 ⌋ + 2 it follows from the case for v + 1 (odd) and w -1 = ⌊ v+4 6 ⌋ + 1 ≤ v+1+9 6 , and δ min (v + 1, w -1) = 0 v+w . If w ≥ ⌊ v+4 6 ⌋ + 3 it follows from the case for v + 2 (even) and w -2.

Let v be odd. If w = ⌊ v+9 6 ⌋ + 1 it follows from the case for v + 1 (even) and w -1, which has been already proved (in this case also

6 ⌋ + 2 it follows from the case for v + 2 (odd) and w -2.

In each case, we use the same general prescription. Given a partial triple system (V, B), a headset S = {s 1 , . . . , s b } is formed using Lemma 5.2. Add vertices W = {a 0 , . . . , a w-1 }, a set disjoint from V of size w ≥ 1. For each i let D i be a subset of {0, . . . , w -1}, which is specified for each subcase, and that satisfies the following property : |D i | is at most the number of occurrences of i in the headset S . Among the blocks B k such that s k = i, we choose |D i | of them, namely the subset {B j k : j ∈ D i }, and form |D i | kites by adding for each j ∈ D i the edge {a j , i} to the block B j k . The idea behind the construction is that if we can choose |D i | = w, we use all the edges between V and W leaving a minimum number of triangles in the partition of V (see Case O1a). Unfortunately it is not always possible to choose |D i | = w, in particular when w is greater than the number of occurrences of i in the headset. So we distinguish different cases :

6 . Let (V, B) be a Steiner triple system. For 0 ≤ i < v, let D i = {0, . . . , w -1}. Apply the general prescription. If v = 6t + 1, i appears t times in S and w ≤ v-1 6 = t. If v = 6t + 3, i appears t or t + 1 times in S and w ≤ t. In both cases |D i | is at most the number of occurrences of i in S , so the construction applies and all the edges between V and W are used in the kites. All the edges on V are used and v(v-1)

6

vw triangles remain. Finally, it remains to partition the edges of W. When w {2, 4}, form a M ON (w, 4) on W, and doing so we have at most δ min triangles. If w = 2 or w = 4 remove edges {a 0 , 0} and {a 1 , 0} from their kites and partition K W together with these edges into a triangle (w = 2) or two kites (w = 4). Case O1b. v = 6t + 5 and w ≤ v-1 6 . Form a partial triple system (V, B) covering all edges except those in the C 4 (0, 1, 2, 3). For 0 ≤ i ≤ 3, let D i = {0, . . . , w -2} and for 4 ≤ i < v D i = {0, . . . , w -1}. Apply the general prescription. Add the kites (a w-1 , 1, 2; 3) and (a w-1 , 3, 0; 1). Here again i appears at least t times in S and w ≤ t. So D i is at most the number of occurrences of i in S . Again we have used all the edges on V and all the edges between V and W. It remains to partition the edges of W, and this can be done as in the Case O1a. Case O2. v = 6t +3 and w = t +1, v > 3. Form a partial triple system covering all edges except those on the v-cycle {{i, (i + 1) mod v} : 0 ≤ i < v} [START_REF] Colbourn | Quadratic leaves of maximal partial triple systems[END_REF]. Set D i = {1, . . . , w -1} for all i. Apply the general prescription. Adjoin edges from a 0 to a partition of the cycle, minus edge {0, v-1}, into P 3 s. The only edge between V and W that remains is {a 0 , v -1}. When an ON (w, 4) exists having 1, 2, 3, or 4 triangles, this edge is used to convert a triangle to a kite. This handles all cases except when w ∈ {2, 4}. In these cases, remove the pendant edge {a 1 , v -1} from its kite. When w = 2, {a 0 , a 1 , v -1} forms a triangle. When w = 4, partition the edges on W together with {a 0 , v-1} and {a 1 , v-1} into two kites.

Case O3. v = 6t + 1 and w = t + 1.

When t = 1, a M ON (7 + 2, 7; 4, 3) has B = {(0, a 1 , a 0 ; 6), (2, 0, 6; a 1 ), (3, 0, 4; a 1 ), (1, 0, 5; a 1 ), (3, 6, 5; a 0 ), (4, 6, 1; a 1 ), (3, 2, 1; a 0 ), (5, 2, 4; a 0 ), (a 0 , 2, a 1 , 3)}.

A solution with t = 2 is given in Appendix D. When t ≥ 3, form a 3-GDD of type 6 t with groups {{6p + q : 0 ≤ q < 6} : 0 ≤ p < t}. Let D 6p+q = {0, . . . , w -2} \ {p} for 0 ≤ p < t and 0 ≤ q < 6. Apply the general prescription. For 0 ≤ p < t, on {6p + q : 0 ≤ q < 6} ∪ {v -1} ∪ {a w-1 , a p } place a M ON (7 + 2, 7; 4, 3) obtained from the solution B for t = 1, by replacing q by 6p + q : 0 ≤ q < 6, 6 by v -1 a 0 by a w-1 and a 1 by a p ; then omit the kite (a p , 6p, a w-1 ; v -1). All edges on W remain ; the edges {a w-1 , 6p} and {a p , 6p} remain for 0 ≤ p < t, and the edge {a w-1 , v -1} remains.

Add the kites (a w-2 , 6(w -2), a w-1 ; v -1) and for 0 ≤ j < w -2 = t -1 (6 j, a w-1 , a j ; a w-2 ). If w -2 {2, 4}, that is t {3, 5}, place a M ON (w -2, 4) on Wa w-2a w-1 . Note that, as 3 w-2 2 ≡ 3 v+w 2 (mod 4), we have the right number of triangles (at most 3). If w -2 ∈ {2, 4} remove edges {a 0 , w -2} and {a 1 , w -2} from their kites, and partition K w together with these edges.

Case O4. v = 6t + 5 and w = t + 1.

For t = 0, a M ON (5 + 1, 5; 4, 3) has kites (3, a 0 , 0; 1), (1, a 0 , 2; 3), (1, 3, 4; a 0 ), and triangle (0, 2, 4).

For t = 1, let V = {0, . . . , 10} and W = {a 0 , a 1 }. A M ON (11 + 2, 11; 4, 3) is formed by using an M ON (5 + 1, 5; 4, 3) on {0, 1, 2, 3, 4} ∪ {a 0 }, and a partition of the remaining edges, denoted by Q, into 15 kites and a triangle. So we have two triangles, attaining δ min [START_REF] Colbourn | Minimizing SONET ADMs in unidirectional WDM rings with grooming ratio 7[END_REF][START_REF] Bermond | Traffic grooming in unidirectional WDM rings with grooming ratio C = 6[END_REF] as 13 ≡ 5 (mod 8). The partition of Q is as follows : the triangle (a 0 , a 1 , 10) and the kites (0, 6, 5; a 0 ), [START_REF] Bermond | Minimizing SONET ADMs in unidirectional WDM rings with grooming ratio 3[END_REF][START_REF] Bryant | A survey on the existence of G-designs[END_REF][START_REF] Bermond | Traffic Grooming in Unidirectional WDM Ring Networks : the all-to-all unitary case[END_REF]; a 0 ), (2, 9, 7; a 0 ), (3, 10, 8; a 0 ), (4, 6, 9; a 0 ), (8, 9, 0; a 1 ), (5, 7, 1; a 1 ), (5, 8, 2; a 1 ), (6, 7, 3; a 1 ), [START_REF] Bermond | The CRC Handbook of Combinatorial Designs[END_REF][START_REF]Handbook of combinatorial designs[END_REF][START_REF] Bermond | Traffic grooming in unidirectional WDM ring networks using design theory[END_REF]; a 1 ), (3, 9, 5; a 1 ), (2, 10, 6; a 1 ), (0, 10, 7; a 1 ), (4, 7, 8; a 1 ), and (1, 10, 9; a 1 ).

For t = 2, a M ON (17 + 3, 17; 4, 3) is given in Appendix D. For t ≥ 3, form a 3-GDD of type 6 t with groups {{6p + q : 0 ≤ q < 6} : 0 ≤ p < t}. Let D 6p+q = {0, . . . , w -2} \ {p} for 0 ≤ p < t and 0 ≤ q < 6. Apply the general prescription. There remain uncovered for each p the edges of the set Q p obtained from the complete graph on the set of vertices {6p

To deal with the edges of Q p , we start from a partition of Q, where we replace pendant edges in kites as follows : Replace {a 1 , 4} by {a 1 , 10}, {a 0 , 8} by {a 0 , 10}, and {a 1 , 2} by {a 0 , 8}. We delete the triangle (a 0 , a 1 , 10), resulting in a new partition of Q into 15 kites and the 3 edges {a 0 , a 1 }, {a 1 , 2}, and {a 1 , 4}. Then we obtain a partition of Q p by replacing {0, 1, 2, 3, 4} by {v -5, v -4, v -3, v -2, v -1}, q + 5 by 6p + q for 0 ≤ q < 6, a 0 by a w-1 , and a 1 by a p . At the end we get a partition of Q p into 15 kites plus the 3 edges {a w-1 , a p }, {a p , v -3}, and {a p , v -1}.

INRIA

Now the 3t edges {{a w-1 , a p }, {a p , v -3}, {a p , v -1} : 0 ≤ p < t} plus the uncovered edges of K W form a K t+3 missing a triangle on {a w-1 , v -3, v -1}. If t + 3 ≡ 2, 3, 4, 5, 6, 7 (mod 8), use Theorem 2.1 to form a ON (t + 3, 4) having a triangle (v -3, v -1, a w-1 ) and 0, 1, or 2 other triangles ; remove the triangle (v -3, v -1, a w-1 ) to complete the solution with 1, 2, or 3 triangles (the triangle (v -5, v -3, v -1) is still present). A variant is needed when t + 3 ≡ 0, 1 (mod 8). In these cases, form a ON (t + 3, 4) (having no triangles) in which (v -3, a w-1 , v -1; a 1 ) is a kite. Remove all edges of this kite, and use edge {a 1 , v -1} to convert triangle (v -5, v -3, v -1) to a kite.

Finally, place a M ON (5 + 1, 5; 4, 3) on {v -5, v -4, v -3, v -2, v -1} ∪ {a 0 }. Altogether we have a partition of all the edges using at most 3 triangles.

Case O5. v = 6t + 5 and w = t + 2.

When t = 0, partition all edges on {0, 1, 2, 3, 4} ∪ {a 0 , a 1 } except {a 0 , a 1 } into kites (3, 1, a 0 ; 0), (3, 2, a 1 ; 0), (a 1 , 1, 4; 2), (0, 1, 2; a 0 ), and (3, 0, 4; a 0 ). Then a M ON (5 + 2, 5; 4, 3) is obtained by removing pendant edges {a 0 , 0} and {a 1 , 0} and adding triangle (a 0 , a 1 , 0).

When t = 1, a M ON (11+3, 11; 4, 3) on {0, . . . , 10}∪{a 0 , a 1 , a 2 } is obtained by taking the above partition on {0, 1, 2, 3, 4} ∪ {a 0 , a 1 }, the triangle (a 0 , a 1 , a 2 ), and a partition of the remaining edges (which form a graph called Q) into 11 kites and 6 4-cycles as follows : kites (2, 9, 7; a 0 ), (4, 5, 10; a 0 ), (2, 10, 6; a 1 ), (4, 6, 9; a 2 ), (7, 10, 0; a 2 ), (6, 8, 1; a 2 ), (5, 8, 2; a 2 ), (5, 9, 3; a 2 ), (7, 8, 4; a 2 ), (6, 7, 5; a 2 ), and (9, 10, 8; a 1 ) ; and 4-cycles (0, 6, a 0 , 5), (0, 8, a 0 , 9), (1, 5, a 1 , 7), (1, 9, a 1 , 10), (3, 6, a 2 , 7), and (3, 8, a 2 , 10).

A solution with t = 2 is given in Appendix D. When t ≥ 3, form a 3-GDD of type 6 t with groups {{6p + q : 0 ≤ q < 6} : 0 ≤ p < t}. Let D 6p+q = {0, . . . , w -3} \ {p} for 0 ≤ p < t and 0 ≤ q < 6. Apply the general prescription. Add a partition of the complete graph on {v -5, v -4, v -3, v -2, v -1} ∪ {a w-2 , a w-1 } as in the case when t = 0. It remains to partition, for each p, 0 ≤ p < t, the graph Q p is obtained from the complete graph on {6p + q : 0 ≤ q < 6} ∪ {v -5, v -4, v -3, v -2, v -1} ∪ {a w-2 , a w-1 , a p } minus the complete graph on {v -5, v -4, v -3, v -2, v -1} ∪ {a w-2 , a w-1 }. This partition is obtained from that of Q by replacing {0, 1, 2, 3, 4} by {v -5, v -4, v -3, v -2, v -1}, a 0 by a w-2 , a 1 by a w-1 , and a 2 by a p . What remains is precisely the edges on W, so place a M ON (w, 4) on W to complete the construction.

Case O6. v = 6t + 3 and w = t + 2.

When t = 0, a M ON (3+2, 3; 4, 3) has triangles (a 0 , 0, 1) and {a 1 , 1, 2} and 4-cycle (0, 2, a 0 , a 1 ). When t = 1, on {0, . . . , 8}∪{a 0 , a 1 , a 2 }, place kites (2, 6, 4; a 0 ), (0, 8, 4; a 1 ), (0, 5, 7; a 1 ), (3, 6, 0; a 2 ), (1, 7, 4; a 2 ), (5, 8, 2; a 2 ), (1, 6, 5; a 2 ), (2, 7, 3; a 2 ), (3, 8, 1; a 2 ), (3, 5, a 0 ; a 2 ), (7, a 0 , 6; a 2 ), (6, 8, a 1 ; a 2 ), (7, a 2 , 8; a 0 ), and 4-cycle (3, 4, 5, a 1 ). Adding the blocks of a M ON (3+2, 3; 4, 3) forms a M ON (9+ 3, 9; 4, 3).

A solution with t = 2 is given in Appendix D. When t ≥ 3, form a 3-GDD of type 6 t with groups {{6p + j : 0 ≤ q < 6} : 0 ≤ p < t}. Let D 6p+q = {0, . . . , w -3} \ {p} for 0 ≤ p < t and 0 ≤ q < 6. Apply the general prescription. For 0 ≤ p < t, on {6p +q : 0 ≤ q < 6}∪{v-3, v-2, v-1}∪{a w-2 , a w-1 , a p } place a M ON (9 +3, 9; 4, 3), omitting a M ON (3 + 2, 2; 4, 3) on {a w-2 , a w-1 , v -3, v -2, v -1}. Place a M ON (3 + 2, 2; 4, 3) on {a w-2 , a w-1 , v -3, v -2, v -1}. Remove edges {a 0 , a w-2 } and {a 1 , a w-1 } from their kites, and convert


PhD student, 3rd Laura Lepage
email: laura.lepage@univ-lorraine.fr

Fabienne Lemétayer

The patient-physician relationship across therapeutic observance and their expectations of treatment : preliminary results of a qualitative approach

The patient physician relationship across therapeutic observance and their expectations of treatment

Laura Lepage, Fabienne Lemétayer

Introduction

Method

Results

Conclusion

▪ Osteoporosis is a chronic bone disease that is asymptomatic until the first fracture. The asymptomatic nature of osteoporosis leads patients to have more questions about the need for treatment and to have higher expectations.

▪ Patients expect treatment to improve their health and wellbeing, but to continue to meet their current needs and not interfere with their personal goals.

▪ Rheumatologists, on the other hand, assess these expectations of treatment in terms of prevention, limitation of disease and clinical outcomes. ▪In general, osteoporotic patients have higher expectations of treatment than their rheumatologists.

▪Patients express expectations that their health will improve so that they can continue their life goals. The rheumatologists' expectations are related to the benefits of the treatment and the efforts to be made by the patients.

▪Factors such as their beliefs about side effects or treatments in general increase expectations and make it difficult for patients to adapt to treatment. For rheumatologists, the lack of feedback from patients makes it more difficult to identify and understand what their patients expect from the treatment.

Objectif : To examine the expectations of patients and their rheumatologists of anti-osteoporosis treatment, and their influence on the doctor-patient relationship.

Osteoporotic patients Rheumatologists

Patient-physician relationship

Expectations of current treatment

Expectations about the end of treatment

General expectations

Perceived benefits

(2 references)

Positive effects on bone structure (25 references)

Life goals (4 references)

Perceived benefits (3 references)

Need for information on the duration of treatment (8 references)

Awareness of benefits/risks

(5 references)

➢Figure 1 :

 1 Figure 1 : Expectations of osteoporotic patients and their rheumatologists regarding treatment for osteoporosis.

Figure

  Figure 2 : Factors reinforcing the difficulties encountered by osteoporotic patients and their rheumatologists in meeting their mutual treatment expectations.


Xiuqi Wu

Junsong Peng
email: jspeng@lps.ecnu.edu.cn

Sonia Boscolo

Christophe Finot

Heping Zeng
email: hpzeng@phy.ecnu.edu.cn

Synchronisation, desynchronisation and intermediate regime of breathing solitons and soliton molecules in a laser cavity

HAL is

avenues for the study of nonlinear synchronisation dynamics.

First recognised in 1665 by Christiaan Huygens in a letter to his father [START_REF] Huygens | Oeuvres Complètes de Christiaan Huygens[END_REF], synchronisation, i.e., the ability of coupled oscillators to lock to a common frequency, is a general and ubiquitous feature of nature, occurring for biological clocks, chemical reactions, mechanical or electrical oscillators, and lasers to mention a few well-known examples [START_REF] Pikovsky | Synchronization: A Universal Concept in Nonlinear Science[END_REF]. Apart from being of significant interest in fundamental science, synchronisation phenomena also find a wide range of practical applications. For instance, in the field of optics, the synchronisation of multiple micro-resonators can break the power limitation of a single microresonator [START_REF] Jang | Synchronization of coupled optical microresonators[END_REF][START_REF] Kim | Synchronization of nonsolitonic Kerr combs[END_REF][START_REF] Kim | Coherent combining for high-power Kerr combs[END_REF]. Breathing solitons, manifesting themselves as localised temporal or spatial structures that exhibit periodic oscillatory behaviour, are fundamental modes of many nonlinear physical systems and relate to a wide range of important nonlinear dynamics. In optics, initially studied in single-pass fibre systems [START_REF] Dudley | Instabilities, breathers and rogue waves in optics[END_REF][START_REF] Xu | Breather wave molecules[END_REF], the breathing soliton concept has been extended to passive Kerr cavities and microresonators [START_REF] Leo | Dynamics of one-dimensional Kerr cavity solitons[END_REF][START_REF] Cole | Subharmonic entrainment of Kerr breather solitons[END_REF][START_REF] Lucas | Breathing dissipative solitons in optical microresonators[END_REF][START_REF] Yu | Breather soliton dynamics in microresonators[END_REF] as well as to ultrafast fibre lasers [START_REF] Soto-Crespo | Bifurcations and multipleperiod soliton pulsations in a passively mode-locked fiber laser[END_REF][START_REF] Peng | Breathing dissipative solitons in mode-locked fiber lasers[END_REF][START_REF] Xian | Subharmonic entrainment breather solitons in ultrafast lasers[END_REF][START_REF] Wu | Intelligent breathing soliton generation in ultrafast fiber lasers[END_REF][START_REF] Du | Spatio-spectral dynamics of the pulsating dissipative solitons in a normal-dispersion fiber laser[END_REF][START_REF] Liu | Visualizing the "invisible" soliton pulsation in an ultrafast laser[END_REF][START_REF] Krupa | Real-time observation of double-Hopf bifurcation in an ultrafast all-PM fiber laser[END_REF][START_REF] Wang | Spectral pulsations of dissipative solitons in ultrafast fiber lasers: Period doubling and beyond[END_REF][START_REF] Du | Emergent phenomena of vector solitons induced by the linear coupling[END_REF][START_REF] Wu | Farey tree and devil's staircase of frequency-locked breathers in ultrafast lasers[END_REF][START_REF] Peng | Breather molecular complexes in a passively mode-locked fiber laser[END_REF][START_REF] Guo | Concurrent passive mode-locked and self-Q-switched operation in laser systems[END_REF][START_REF] Cui | Dichromatic "breather molecules" in a mode-locked fiber laser[END_REF]. The studies in [START_REF] Cole | Subharmonic entrainment of Kerr breather solitons[END_REF][START_REF] Xian | Subharmonic entrainment breather solitons in ultrafast lasers[END_REF] have shown that cavitybased optical systems can support breather oscillations that are sub-harmonically entrained to the cavity roundtrip time. This sub-harmonic entrainment of breathers, which is a generalised form of synchronisation wherein a harmonic of the breathing frequency fb synchronises with the cavity frequency fr, results from the competition between the two intrinsic frequencies to the system fr and fb. In [START_REF] Wu | Farey tree and devil's staircase of frequency-locked breathers in ultrafast lasers[END_REF], we have reported frequency locking at Farey fractions of a breather fibre laser by demonstrating for the first time that the winding numbers fb/fr show the hierarchy of a Farey tree and the structure of a devil's staircase, in accordance with the predictions from the theory of nonlinear systems with two competing frequencies [START_REF] Jensen | Complete devil's staircase, fractal dimension, and universality of mode-locking structure in the circle map[END_REF].

These breather synchronisation studies pertain to the dynamics of single breathers. In like manner to their stationary counterparts [START_REF] Malomed | Bound solitons in the nonlinear Schrödinger-Ginzburg-Landau equation[END_REF][START_REF] Stratmann | Experimental observation of temporal soliton molecules[END_REF][START_REF] Krupa | Real-time observation of internal motion within ultrafast dissipative optical soliton molecules[END_REF][START_REF] Herink | Real-time spectral interferometry probes the internal dynamics of femtosecond soliton molecules[END_REF][START_REF] Peng | Build-up of dissipative optical soliton molecules via diverse soliton interactions[END_REF][START_REF] Liu | Real-time observation of the buildup of soliton molecules[END_REF], multiple interacting breathing solitons in dissipative systems can also organise themselves into molecule-like bound states [START_REF] Lucas | Breathing dissipative solitons in optical microresonators[END_REF][START_REF] Peng | Breathing dissipative solitons in mode-locked fiber lasers[END_REF][START_REF] Peng | Breather molecular complexes in a passively mode-locked fiber laser[END_REF]. It remains elusive whether breather molecular complexes also display synchronisation. Furthermore, while single breather oscillations in a laser represent a convenient nonlinear dynamical system to study two-frequency interactions [START_REF] Wu | Farey tree and devil's staircase of frequency-locked breathers in ultrafast lasers[END_REF], multibreather complexes add new degrees of freedom into the system -the breathing frequencies of the elementary constituents -thereby opening the possibility to study the dynamics of nonlinear systems with three or more interacting frequencies, which is an important topic in nonlinear science [START_REF] Grebogi | Are three-frequency quasiperiodic orbits to be expected in typical nonlinear dynamical systems?[END_REF][START_REF] Held | Quasiperiodic transitions to chaos of instabilities in an electronhole plasma excited by ac perturbations at one and at two frequencies[END_REF][START_REF] Cumming | Quasiperiodicity and chaos in a system with three competing frequencies[END_REF][START_REF] Cartwright | Universality in three-frequency resonances[END_REF].

In this Letter, we present the results of a further study showing that breather molecules can synchronise to a laser cavity, featuring a breathing frequency that equals a subharmonic of the cavity fundamental frequency. In the desynchronised phase, while the breather molecule as whole is not synchronised to the cavity, lag synchronisation among the constituent breathers is observed. An intermediate regime between the synchronised and desynchronised phases is also observed, featuring a subharmonic breathing frequency with non-subharmonic sidebands. Direct synchronisation-desynchronisation transitions without such a regime occur when the intracavity loss is increased. The transitions among these different phases are realised by tuning a single control parameter (the pump current). These experimental findings are confirmed by numerical simulations of a lumped laser model.

The system that we studied is a standard mode-locked fibre laser (Fig. 1). The gain medium is a 1.24 m-long erbium-doped fibre. Other fibres in the cavity are single-mode fibres. The group-velocity dispersion (GVD) parameters of the two fibre types are 61.2 and -18 ps 2 /km, respectively, resulting in a slightly anomalous net cavity dispersion (-0.0078 ps 2 ). The laser has a repetition frequency of fr = 33.39 MHz.

Mode locking is realised through an effective saturable absorber by the nonlinear polarisation evolution (NPE) effect [START_REF] Noske | Subpicosecond soliton pulse formation from self-modelocked erbium fibre laser using intensity dependent polarisation rotation[END_REF]. The transfer function of NPE is controlled via three wave plates working together with a polarisation beam splitter which also serves as the laser output port. The pump strength is the key parameter of the system: its tuning under given settings of the wave plates may enable switching from stationary soliton to breathing soliton states [START_REF] Peng | Breathing dissipative solitons in mode-locked fiber lasers[END_REF][START_REF] Xian | Subharmonic entrainment breather solitons in ultrafast lasers[END_REF][START_REF] Wu | Intelligent breathing soliton generation in ultrafast fiber lasers[END_REF][START_REF] Du | Spatio-spectral dynamics of the pulsating dissipative solitons in a normal-dispersion fiber laser[END_REF][START_REF] Liu | Visualizing the "invisible" soliton pulsation in an ultrafast laser[END_REF][START_REF] Krupa | Real-time observation of double-Hopf bifurcation in an ultrafast all-PM fiber laser[END_REF][START_REF] Wang | Spectral pulsations of dissipative solitons in ultrafast fiber lasers: Period doubling and beyond[END_REF][START_REF] Du | Emergent phenomena of vector solitons induced by the linear coupling[END_REF][START_REF] Wu | Farey tree and devil's staircase of frequency-locked breathers in ultrafast lasers[END_REF][START_REF] Peng | Breather molecular complexes in a passively mode-locked fiber laser[END_REF][START_REF] Guo | Concurrent passive mode-locked and self-Q-switched operation in laser systems[END_REF][START_REF] Cui | Dichromatic "breather molecules" in a mode-locked fiber laser[END_REF][START_REF] Peng | Experimental observations of breathing dissipative soliton explosions[END_REF][START_REF] Peng | Triple-state dissipative soliton laser via ultrafast self-parametric amplification[END_REF][START_REF] Zhou | Breathing dissipative soliton molecule switching in a bidirectional mode-locked fiber laser[END_REF] or to soliton molecules (SMs) with various dynamics [START_REF] Krupa | Real-time observation of internal motion within ultrafast dissipative optical soliton molecules[END_REF][START_REF] Hamdi | Superlocalization reveals longrange synchronization of vibrating soliton molecules[END_REF][START_REF] Zou | Synchronization of the internal dynamics of optical soliton molecules[END_REF][START_REF] Liu | On-demand harnessing of photonic soliton molecules[END_REF]. Contrary to our previous works [START_REF] Wu | Intelligent breathing soliton generation in ultrafast fiber lasers[END_REF][START_REF] Wu | Farey tree and devil's staircase of frequency-locked breathers in ultrafast lasers[END_REF] and to reduce as much as possible the intracavity loss, we have not implemented any genetic algorithm in the present laser. Indeed, the frequency locking dynamics of breather molecular complexes have been found to be highly affected by cavity damping (see Fig. S1 in the Supplementary Information). Figure 2 illustrates how the radiofrequency (RF) spectrum of the laser emission (measured by a radio spectrum analyser connected to photodiode 3 in Fig. 1) is influenced by the pump current (see also the measurements across a frequency range up to fr provided in Fig. S2 of the Supplementary Information).

At low currents (up to 102 mA), our laser emits a single soliton pulse per cavity roundtrip (RT) as evidenced by the single frequency component of the RF signal at fr (Supplementary Information Fig. S2). Increase of the pump current leads to the generation of a breathing soliton with a short pulsating period of 4 RTs, as revealed by the appearance the subharmonic narrow peaks located at multiples of fb = fr /4: the breathing frequency fb is locked to the cavity repetition frequency [START_REF] Wang | Spectral pulsations of dissipative solitons in ultrafast fiber lasers: Period doubling and beyond[END_REF][START_REF] Wu | Farey tree and devil's staircase of frequency-locked breathers in ultrafast lasers[END_REF]. The transition from stationary to breathing soliton correlates to the ubiquitous dynamics known as "Hopf bifurcation". Further pump current increase causes new equally spaced spectral lines to appear symmetrically on both sides the subharmonic peaks.

The separation f'b between these new lines, forming a "modulated subharmonic" structure, is associated with a long pulsating period in the time domain. Pump currents above 106 mA break the frequency locking (the modulated sidebands also vanish), and the breathing frequency continuously drifts as the pump strength varies so that fb is no longer commensurate with fr. We term this laser regime "non-subharmonic breathing". For currents above 111 mA, the pulsating regime disappears, being replaced by a short stage of chaotic-like behavior and then the emission of stationary diatomic SMs up to 117 mA, when pulsating pulses are generated again in the form of breathing SMs. Between 120 and 123 mA, subharmonic and modulated subharmonic behaviors are retrieved whereas non-harmonic features are apparent between 117 and 120 mA and then between 123 and 133 mA. Above 133 mA, the diatomic breathing SM switches to a triatomic molecule, and a similar evolution pattern of the RF spectrum from subharmonic to modulated subharmonic and to non-subharmonic breathing is again recorded. Our experimental observations emphasise the robustness of the phase transition phenomenon, which is independent of the number of elementary constituents of the breathing soliton structure. To enlighten the laser dynamics in the different phases, we have focused on the case of the diatomic breathing SM that is observed for pump currents in the range 117 to 134 mA. The case of the triatomic breather molecule is illustrated in Fig. S3 of the Supplementary Information, displaying qualitatively similar features. We have complemented the RF spectrum measurements by additional spatio-spectral measurements, which are summarised in Fig. 3. Panels (a-c) therein show the roundtrip-resolved optical spectra measured by the time-stretch technique [START_REF] Goda | Dispersive Fourier transformation for fast continuous single-shot measurements[END_REF][START_REF] Runge | Coherence and shot-toshot spectral fluctuations in noise-like ultrafast fiber lasers[END_REF][START_REF] Mahjoubfar | Time stretch and its applications[END_REF][START_REF] Godin | Recent advances on time-stretch dispersive Fourier transform and its applications[END_REF] (photodiode 1 in Fig. 1) for the three breathing regimes. Periodic variations of the spectral intensity across a well-defined period of 4 cavity RTs can be observed for the subharmonic regime (Fig. 3a), accompanied by corresponding synchronous periodic changes of the pulse energy (white curve). By contrast, the non-subharmonic regime (Fig. 3b) shows degraded periodicities in both the optical spectrum and energy. The spectra recorded at the RT numbers of maximal and minimal energy within a period (Figs. 3e and3f) indicate a larger modulation depth for the non-subharmonic state. In both regimes, the period of spectral fringes remains almost unchanged over cavity RTs: the two breathers within the molecule have nearly equal separation, estimated to be 5.5 ps, which does not change over cavity RTs.

The modulated subharmonic regime shown in Fig. 3d (close-up of Fig. 3c) features two sets of periodicities with a long period of approximately 88 cavity RTs and a short period of 4 RTs. The details of the corresponding RF spectra in the vicinity of fr/4 shown in Fig. 3g further highlight the differences among the three regimes: the subharmonic state features a single very narrow frequency component located exactly at fb=fr/4, while a set of equally spaced narrow sidebands on both sides of fb=fr/4 is observed for the modulated subharmonic case. In sharp contrast to this, the non-subharmonic regime presents much broader spectral lines, confirming the frequency unlocked operation of the laser (see also Fig. S4 in the Supplementary Information for a magnification of Fig. 3g). To validate our experimental findings and gain a better insight into the complex temporal dynamics of breathing SMs, we have performed numerical simulations of the laser based on a lumped model which models each part of the laser cavity separately. Pulse propagation in the optical fibres is modelled by a generalised nonlinear Schrödinger equation (NLSE), which includes the effects of GVD and self-phase modulation for all the fibres, and gain saturation and bandwidth-limited gain for the active fibre. In the scalar-field approach, this equation takes the form [START_REF] Wu | Farey tree and devil's staircase of frequency-locked breathers in ultrafast lasers[END_REF][START_REF] Krupa | Real-time observation of internal motion within ultrafast dissipative optical soliton molecules[END_REF][START_REF] Peng | Build-up of dissipative optical soliton molecules via diverse soliton interactions[END_REF][START_REF] Haus | Mode-locking of lasers[END_REF][START_REF] Mao | Synchronized multiwavelength soliton fiber laser via intracavity group delay modulation[END_REF][START_REF] Liu | Revealing the transition dynamics from Q switching to mode locking in a soliton laser[END_REF][START_REF] Peng | Real-time observation of dissipative soliton formation in nonlinear polarization rotation modelocked fibre lasers[END_REF]]

𝜓𝜓 𝑧𝑧 = - 𝑖𝑖𝛽𝛽 2 2 𝜓𝜓 𝑡𝑡𝑡𝑡 + 𝑖𝑖𝑖𝑖|𝜓𝜓| 2 𝜓𝜓 + 𝑔𝑔 2 �𝜓𝜓 + 1 Ω 2 𝜓𝜓 𝑡𝑡𝑡𝑡 �, (1)
where 𝜓𝜓 = 𝜓𝜓(𝑧𝑧, 𝑡𝑡) is the slowly varying electric field moving at the group velocity along the propagation coordinate z, and 𝛽𝛽 2 and 𝑖𝑖 are the GVD and Kerr nonlinearity coefficients, respectively. The dissipative terms in Eq. ( 1) represent linear gain as well as a parabolic approximation to the gain profile with the bandwidth Ω. The gain is saturated according

𝑔𝑔(𝑧𝑧) = 𝑔𝑔 0 /[1 + 𝐸𝐸(𝑧𝑧) 𝐸𝐸 sat ⁄ ],
where g0 is the small-signal gain, 𝐸𝐸(𝑧𝑧) = ∫ d𝑡𝑡|𝜓𝜓| 2 is the pulse energy, and 𝐸𝐸 sat is the gain saturation energy. We note that 𝐸𝐸 sat can be used to change the pulse energy in the numerical simulations, thus playing a similar role to the pump current in the experiment. To match the numerical and experimental pulse energies to the same scale however, rate equations governing the laser gain dynamics should be included into the numerical model.

The discrete effects of the effective nonlinear saturation involved in the NPE mode-locking technique are modelled by an instantaneous and monotonous nonlinear transfer function for the field amplitude:

𝑇𝑇 = �1 -𝑞𝑞 0 -𝑞𝑞 m [1 + 𝑃𝑃(𝑡𝑡) 𝑃𝑃 s ⁄ ] ⁄
, where q0 is the unsaturated loss due to the absorber, qm is the saturable loss (modulation depth), 𝑃𝑃(𝑧𝑧, 𝑡𝑡) = |𝜓𝜓(𝑧𝑧, 𝑡𝑡)| 2 is the instantaneous pulse power, and Ps is the saturation power.

The numerical model is solved with a standard split-step propagation algorithm and uses similar parameters to the experimental values (Supplementary Table 1). The RF spectrum can be obtained by Fourier transformation of the pulse energy in the simulations. The RF spectral intensity as a function of the gain saturation energy plotted in Fig. 4a shows good agreement with the experimental results (Fig. 2) and confirms the existence of an intermediate modulated subharmonic breathing state between the subharmonic and non-subharmonic phases. One may see that compared to the experiments, the simulations tend to overestimate the range of existence of the chaoticlike regime occurring between single and multi-pulse laser emissions. Such a discrepancy can be ascribed to the extremely large parameter space used in the simulations. By increasing the linear intracavity loss in the model or, equivalently, by changing the polarisation state of the laser in the experiments, direct synchronisation-desynchronisation transitions (without the intermediate state) can also be observed in our breather laser (Supplementary Fig. S5). Such direct transitions are saddle-node bifurcations [START_REF] Pikovsky | Synchronization: A Universal Concept in Nonlinear Science[END_REF]. The experiments (Fig. 2) and simulations (Fig. 4a) also reveal another interesting phenomenon: the higher the number of elementary constituents, the more robust the subharmonic breather structures against pump power (gain saturation energy) variations. Details are given in Fig. S6 of the Supplementary Information.

The roundtrip evolutions of the temporal intensity profiles of subharmonic, non-subharmonic and modulated subharmonic diatomic breathing SMs are shown in panels (b-d) of Fig. 4, respectively. The corresponding spectral evolutions are given in the Supplementary Information (Fig. S7). The evolutions of the peak intensities of the leading and trailing pulses in the subharmonic breathing SM (Fig. 4f) reveal that the two breathers are synchronised to each other. Whilst non-subharmonic breathing SMs are quasiperiodic, there is a constant delay (of 2 cavity RTs) between the two breathers (Fig. 4c), and by adding this delay to the trailing pulse, the evolutions of the two pulses become synchronous (Fig. 4g). This suggests that the dynamics of the two pulses pertains to lag synchronisation, which has been extensively studied in chaotic systems [START_REF] Pikovsky | Synchronization: A Universal Concept in Nonlinear Science[END_REF][START_REF] Rosenblum | From phase to lag synchronization in coupled chaotic oscillators[END_REF][START_REF] Sosnovtseva | Loss of lag synchronization in coupled chaotic systems[END_REF][START_REF] Taherion | Observability of lag synchronization of coupled chaotic oscillators[END_REF][START_REF] Heil | Chaos synchronization and spontaneous symmetry-breaking in symmetrically delay-coupled semiconductor lasers[END_REF]. Modulated subharmonic breathing SMs also show lag synchronisation (Fig. 4h). Furthermore, we have also observed lag synchronisation in the dynamics of triatomic breathing SMs. The evolutions of the temporal intensity profiles (Fig. 4b-e) highlight a general feature of the three breathing SM states: each breather within the molecule is split into multiple sub-pulses, which arises from higher-order soliton-like evolution inside the anomalous dispersion segment of the laser cavity (see Fig. S8 and S9 in the Supplementary Information).

In conclusion, we have observed subharmonic and non-subharmonic breathing soliton structures in an ultrafast fibre laser in both experiments and numerical simulations. We have also unveiled the existence of an intermediate state -modulated subharmonic breathing -between the two phases. These findings could stimulate parallel research on the synchronisation of other coupled nonlinear systems where such a state has not been found yet. Furthermore, our results show that transitions among the three states are not restricted to a single-breather laser emission regime, but alike transitions also occur when the laser operates in a diatomic or triatomic breather SM generation regime, which further substantiates the universal nature of synchronisation/desynchronisation phenomena and opens the possibility to study the dynamics of nonlinear systems with three or more interacting frequencies. Mode-locked fibre lasers are very general physical platforms wherein the fibre propagation dynamics are governed by a generalised NLSE. This equation arises in many physical settings including, but not limited to, Bose-Einstein condensates, surface gravity waves, and superconductivity. Therefore, it is reasonable to assume that similar transitions may also arise in these physical systems when a feedback mechanism is included.

Following the long history of analogies established between nonlinear fibre lasers and the various states of matter with the establishment of the concepts of molecules, crystals, rains, and gases of optical solitons amongst the others [START_REF] Amrani | Dissipative solitons compounds in a fiber laser. Analogy with the states of the matter[END_REF], one can also imagine to qualitatively relate the synchronisation/desynchronisation of breathing solitons and breather molecular complexes reported in this paper with commensurate-incommensurate phase transitions [56], which are ubiquitous phenomena in many areas of condensed-matter physics and beyond.

Fig. 1

 1 Fig. 1 The laser setup. LD laser diode, WDM wavelength-division multiplexer, EDF erbium-doped fibre, ISO isolator, SMF single-mode fibre, Col collimator, QWP quarter-wave plate, HWP half-wave plate, PBS polarisation beam splitter, OC optical coupler, NDF normally dispersive fibre, PD photodetector, OSC oscilloscope, RSA radio spectrum analyser, OSA optical spectrum analyser.

Fig. 2 .

 2 Fig. 2. Map of the laser spectral intensity in the space of RF and pump current, showing phase transitions for single breathers, and diatomic and triatomic breathing SMs. SUB subharmonic, N-SUB non-subharmonic, M-SUB modulated subharmonic.

Fig. 3 .

 3 Fig. 3. Experimental observation of subharmonic, modulated subharmonic, and non-subharmonic diatomic breathing SMs. (ac) Time stretch recording of single-shot optical spectra over consecutive cavity RTs. The white curves denote the energy evolutions. (d) A magnified version of (c) showing the short period breathing. (e,f) Single-shot spectra at the RT numbers of maximal and minimal energies within a period (indicated by dashed lines in (a) and (b), respectively). (g) RF spectrum measurements for the three breathing regimes shown on a reduced frequency span centered on fr/4.

Fig. 4 .

 4 Fig. 4. Numerical modelling results. (a) Transitions among different laser states in the space of RF and gain saturation energy. (b-d) Temporal evolutions of the intensity over consecutive cavity RTs for subharmonic, non-subharmonic and modulated subharmonic diatomic breathing SMs, respectively. Close-up views of the evolutions for the modulated subharmonic breathing SM are shown in panel (e). (f-h) Evolutions of the peak intensities of the leading and trailing breathers for the three breather molecule states. The trailing pulse is delayed by a certain number of RTs in the non-subharmonic and modulated subharmonic states to evidence the synchronisation of the two breathers. (i) RF spectra of the three breather molecule states. Please, change 'chaos-like' to 'chaotic-like'.

Acknowledgement

We acknowledge support from the National Natural Science Fund of China (11621404, 11561121003, 11727812, 61775059, 12074122, 62022033 and 11704123), Shanghai Municipal Science and Technology Major Project (2019SHZDZX01-ZX05), Shanghai Rising-Star Program and Science and Technology Innovation Program of Basic Science Foundation of Shanghai (18JC1412000), the Agence Nationale de la Recherche (ANR-20-CE30-004), the UK Engineering and Physical Sciences Research Council (CREATE -EP/X019241/1), Sustainedly Supported Foundation by National Key Laboratory of Science and Technology on Space Microwave under Grant HTKT2022KL504008, and Shanghai Natural Science Foundation (23ZR1419000).