# Traffic Grooming on the Path

Jean-Claude Bermond, Laurent Braud, David Coudert

► To cite this version:

Jean-Claude Bermond, Laurent Braud, David Coudert. Traffic Grooming on the Path. 12th International Colloquium on Structural Information and Communication Complexity (SIROCCO), May 2005, Mont Saint-Michel, France. pp.34-48, 10.1007/11429647_5. inria-00429172

HAL Id: inria-00429172

https://inria.hal.science/inria-00429172

Submitted on 1 Nov 2009

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Traffic Grooming on the Path*

Jean-Claude Bermond†

Laurent Braud‡

David Coudert§

June 20, 2005

**Abstract**

In a WDM network, routing a request consists in assigning it a route in the physical network and a wavelength. If each request uses at most 1/C of the bandwidth of the wavelength, we will say that the grooming factor is C. That means that on a given edge of the network we can groom (group) at most C requests on the same wavelength. With this constraint the objective can be either to minimize the number of wavelengths (related to the transmission cost) or minimize the number of Add Drop Multiplexer (shortly ADM) used in the network (related to the cost of the nodes). Here we consider the case where the network is a path on N nodes, $P_N$. Thus the routing is unique. For a given grooming factor C minimizing the number of wavelengths is an easy problem, well known and related to the load problem. But minimizing the number of ADM's is NP-complete for a general set of requests and no results are known. Here we show how to model the problem as a graph partition problem and using tools of design theory we completely solve the case where C = 2 and where we have a static uniform all-to-all traffic (requests being all pairs of vertices).

# 1 Introduction

Traffic grooming is the generic term for packing low rate signals into higher speed streams (see the surveys [13, 22, 24]). By using traffic grooming, one can bypass the electronics in the nodes for which there is no traffic sourced or destined to it. Typically, in a optical network using wavelength division multiplexing (WDM), instead of having one SONET Add Drop Multiplexer (shortly ADM) on every wavelength at every node, it may be possible to have ADMs only for the wavelength used at that node (the other wavelengths being optically routed without electronic switching). More precisely, in SONET networks, the bandwidth offered by a wavelength (typically 2.5 or 10 Gbits/sec.) is shared by several low speed streams. For instance, an OC-48 corresponds to a bandwidth of 2.5Gbits/sec is a container for 4 OC-12, each corresponding to a 655Mbits/sec stream. In order to manage those bitstream, an ADM is to be placed each time a stream is added or dropped from a wavelength.

In the past many papers on WDM networks had for objective to minimize the transmission cost and in particular the number of wavelengths to be used [1, 2, 11], recent research has focused on reducing the total number of ADMs used in the network, trying to minimize it.

Here, we consider the particular case of paths (the routing is unique) with static uniform all-to-all traffic (requests being all pairs of vertices).

<footnote>*This work has been partially funded by European projects IST FET CRESCO and COST 293 GRAAL, and has been done in the CRC CORSO with France Telecom.</footnote>

<footnote>†Mascotte Project, CNRS/I3S/INRIA – 2004 route des Lucioles – B.P. 93 – F-06902 Sophia-Antipolis Cedex – FRANCE</footnote>

<footnote>‡ENS-Lyon – 46 allée d'Italie – F-69364 Lyon Cedex 07 – FRANCE</footnote>

<footnote>§Corresponding author: David.Coudert@sophia.inria.fr</footnote>
To each request {$i, j$} routed on the path from $i$ to $j$, we want to assign a wavelength in such a way that at most *C* requests use the same wavelength on a given edge of the path. Equivalently, each request uses $1/C$ of the bandwidth of the wavelength. *C* is called the *grooming ratio* (or *grooming factor*). For example, if the request from *i* to *j* is one OC-12 and a wavelength can carry an OC-48, the grooming factor is 4. Given the grooming ratio *C* and the length *N* of the path, the objective is to minimize the total number of (SONET) ADMs used, denoted *A*(*P*<sub>*N*</sub>, *C*), and so reducing the network cost by eliminating as many ADMs as possible from the “no grooming case”.

Figure 1 shows how to groom requests for a grooming factor $C = 2$ and a path $P_N$ with $N = 3, 7, 9$ vertices. For $N = 7$ we have 21 requests. So, a priori, if we give one wavelength to each request we need 42 ADMs. Using the same wavelength for disjoint requests (case $C = 1$) we will see after that 33 ADMs suffice. Indeed two requests may share an ADM if they have a common extremity. For $C = 2$ we will see that the construction given in Figure 1 is optimal and use 20 ADMs (note that 4 requests share the same ADM in vertex 3).

To the best of our knowledge, the problem for paths has only been studied in [10] where it has been proved NP-complete for a general set of requests and no other results are known. Other topologies have also been considered and in particular unidirectional rings primarily in the context of variable traffic requirements [6, 12, 17, 25, 27], but the case of fixed traffic requirements has served as an important special case [2, 3, 4, 5, 13, 15, 16, 19, 20, 22, 26, 28].

In this paper we model the grooming problem on the path as a graph partition problem. Then, we show how a greedy algorithm gives a solution for $C = 1$ and any set of requests. Thus, using tools of design theory, we determine exactly the number of ADMs in the case $C = 2$ for the all-to-all set of requests.

<figure><img src="image_2.png" /><figcaption>Figure 1: Constructions for $N = 3, 7$ and $9$.</figcaption></figure>

## 2 Modelization

Here we are given a physical graph and a set of requests. The physical graph will be the path $P_N$ with vertex set $V = \{0, 1, 2, \dots, N-1\}$ and where the edges are the pairs $\{i, i+1\}, 0 \le i \le N-2$.

The set of requests *I* is a set of pairs {$u, v$} that we model by a graph *G* = (*V*, *E*) where each edge *e* = {$u, v$} is associated to the request {$u, v$}. Each request is routed along the unique subpath from *u* to *v* and we associate to it a wavelength *w*.
For a subgraph $B$ of requests of $G$, we define the load of an edge $e = \{i, i+1\}$ of $P_N$, $L(B, e)$, as the number of requests which are routed through $e$, that is the number of edges $\{u, v\}$ of $B$ such that $u \le i < v$.

Now let $B_w = (V_w, E_w)$ be the subgraph of $G$ containing all requests carried by wavelength $w$. The fact that the grooming ratio is $C$ can be expressed as $L(B_w, e) \le C$ for each edge $e$ of $P_N$. The number of ADMs used for wavelength $w$ is nothing else than $|V_w|$.

So the problem corresponds to partition the edges of $G$ (set of requests) into subgraphs $B_w$ (set of requests with wavelength $w$) such that $L(B_w, e) \le C$.

It is straightforward to see that minimizing the number $W$ of wavelengths needed to route all requests is equivalent to minimize the number of subgraphs in the partition. Furthermore this is an easy problem since the load $L(G, e)$ is easy to compute. For example if $G$ is the complete graph, $L(G, \{i, i+1\}) = (i+1)(N-i-1)$. If $L_{\max}(G)$ is the maximum load over all the edges, $L_{\max}(G) = \max_{e \in P_N} L(G, e)$, then we need at least $\frac{L_{\max}(G)}{C}$ wavelengths and we can assign them in a greedy way. For the complete graph, the number of wavelengths is therefore:

**Proposition 2.1** For the all-to-all set of requests on the path $P_N$ and grooming ratio $C$, the minimum number of wavelength needed is $\lceil \frac{N^2-\epsilon}{4C} \rceil$, where $\epsilon = 1$ when $N$ is odd and $0$ otherwise.

**Proof:** We have $L_{\max}(K_N) = \max_{e \in P_N} L(K_N, e) = \max_{\{i,i+1\}=e \in P_N} (i+1)(N-i-1) = \left\lceil \frac{N^2-\epsilon}{4} \right\rceil$, where $\epsilon = 1$ when $N$ is odd and $0$ otherwise. $\square$

Here our objective is to minimize the number of ADMs, that is the sum of the number of vertices in the $B_w$. Thus the problem can be formalized as follows:

**Problem 2.2 (Grooming problem on the path)**

Inputs : a path $P_N$, a grooming ratio $C$ and a set of requests $I$ modeled by the graph $G = (V, E)$

Output : a partition of the edges of $G$ into subgraphs $B_w = (V_w, E_w)$, $w = 1, \dots, W$, such that $\text{load}(B_w, e) \le C$ for each edge $e$ of $P_N$

Objective : minimize $\sum_{1 \le w \le W} |V_w|$

Here we mainly consider $G = K_N$ and, following [4], we will denote $A(P_N, C)$ the optimal number of ADMs for a grooming ratio $C$ and all-to-all set of requests on the path.

We have formalized the problem in its undirected version, but for paths it is the same for directed or symmetric directed versions. Indeed, if we consider a dipath $\overrightarrow{P_N}$ where the arcs are from $i$ to $i+1$, and if the requests are the couples $(u, v)$, with $u < v$, the problem is exactly the same. If we consider a symmetric dipath $P_N^*$ with arcs $(i, i+1)$ and $(i+1, i)$ and the requests are the couples $(u, v)$, we can split the problem into 2 disjoint subproblems, one with the dipath $\overrightarrow{P_N}$ oriented from 0 to $N-1$ with all requests $(u, v)$ with $u < v$, and the second on the dipath $\overleftarrow{P_N}$ oriented from $N-1$ to 0 with requests $(u, v)$ with $v < u$.

To the best of our knowledge, this problem has only been studied in [10] where it has been proved NP-complete, and no other results are known. However, the grooming problem for rings has been extensively studied. For example in [4] we have shown that the grooming problem on the unidirectional ring can be formalized as follows:
**Problem 2.3 (Grooming problem on the cycle)**

Inputs: a number of nodes $N$ and a grooming ratio $C$

Output: a partition of the edges of $K_N$ into subgraphs $B_w = (V_w, E_w)$, $w = 1, \dots, W$, such that $|E_w| \le C$

Objective: minimize $\sum_{1 \le w \le W} |V_w|$

We denote $A(C_N, C)$ the optimal number of ADMs for a grooming ratio $C$ and all-to-all set of requests on the unidirectional ring.

Note that in Problem 2.3, for the ring, it is supposed that the two requests $(u, v)$ and $(v, u)$ are assigned to the same wavelength (using thus $1/C$ of the capacity of the wavelength). Clearly, a bound on the number of ADMs for unidirectional ring gives a bound for our problem, but there might be very different (for example $A(C_3, 2) = 5$ but $A(P_3, 2) = 3$) due to capacity constraints.

In fact, the problem for unidirectional rings corresponds to the problem of path “with erasure” [10]. In this model a request $(u, v)$ uses $1/C$ of the bandwidth on the whole path and not only on the subpath between $u$ and $v$. The “load condition” becomes: there are at most $C$ requests in any subgraph $B_w$ which is exactly the constraint of Problem 2.3.

We will show in the next section that the grooming problem on the path for $C = 1$ and general instances can be solved polynomially, which is not the case on the ring (in the erasure model) [23, 25, 14].

## 3 Grooming ratio $C = 1$

When the grooming ratio is equal to 1, the grooming problem on the path can be solved optimally for any set of requests in polynomial time. We prove this in Theorem 3.1 and give the exact number of ADMs in the all-to-all case in Corollary 3.2.

**Theorem 3.1** $A(P_N, G, 1) = \sum_{i=0}^{N-1} \max \{d_G^-(i), d_G^+(i)\}$.

**Proof:** The lower bound is simple since in each node $i$ of the path $P_N$ we can not do better than sharing an ADM between a request ending in this node, that is a request $\{u, i\}$ with $u < i$, and a request starting from it, that is $\{i, v\}$ with $i < v$. Thus $A(P_N, G, 1) \ge \sum_{i=0}^{N-1} \max \{d_G^-(i), d_G^+(i)\}$.

Now, note that it is always possible to put a request ending in node $i$ and a request starting from $i$ in a same subgraph. Thus we can form the subgraphs using a greedy process: scan the nodes of the path from 0 to $N-2$ and add to each subgraph containing a request ending in $i$ a requests starting from $i$ (if any left), and then create a new subgraph for each remaining request that start from $i$ (if any). So, in each node $i$, we will use $\max \{d_G^-(i), d_G^+(i)\}$ ADMs and so the lower bound is attained.

Finally, one may remark that this process will create more subgraphs than necessary, but we can merge two subgraphs if they contains disjoint requests. Doing so we will use the optimal number of subgraphs. $\square$

**Corollary 3.2** $A(P_N, 1) = \frac{3N^2-2N-\epsilon}{4}$, where $\epsilon = 1$ when $N$ is odd and 0 otherwise.

A simple construction is the following. First, one can easily check that $A(P_2, 1) = 2$ and $A(P_3, 1) = 5$. Then let the vertices of $P_N$ be 0, 1, ..., $N-1$, arrange them in this order, and suppose that $A(P_N, 1) = (3N^2 - 2N - \epsilon)/4$, where $\epsilon = 1$ when $N$ is odd and 0 otherwise. Let now the vertices of $P_{N+2}$ be $x, 0, 1, \dots, N-1, y$ and arrange them in this order. The subgraphs of the
partition of $K_{N+2}$ will be: the $N$ subgraphs $B_j$, $0 \le j \le N-1$, each of them containing the edges $\{x, j\}$ and $\{j, y\}$, and so $|V(B_j)| = 3$; the subgraph $B_N$ which contains only the edge $\{x, y\}$, and so $|V(B_0)| = 2$; and the subgraphs of the partition of $K_N$. So altogether the partition of $K_{N+2}$ contains $2+3N+(3N^2-2N-\epsilon)/4 = (3(N+2)^2-2(N+2)-\epsilon)/4$, where $\epsilon = 1$ when $N$ is odd and 0 otherwise.

When the grooming ratio is $C \ge 2$, the problem is NP-complete and difficult to approximate for general instance. In particular, when the grooming ratio is equal to $C = 2$, this problem is similar to partition the edges of $G$ into the maximum number of $K_3$ (see [9, 18]), although such partition only provides an upper bound of the total number of ADMs (two $K_3$ may share an ADM). However, for $G = K_N$ we will give in the next sections the exact number of ADMs for $C = 2$.

# 4 Lower bounds

Consider a valid construction for Problem 2.2 and let $a_p$ denote the number of subgraphs of the partition with exactly $p$ nodes, $A$ the number of ADMs, and $W$ the number of subgraphs of the partition. We have the following equalities:

$$A = \sum_{p=2}^{N} pa_p \qquad (1)$$

$$\sum_{p=2}^{N} a_p = W \qquad (2)$$

$$\sum_{w=1}^{W} |E_w| = |E| \qquad (3)$$

In the particular case where $G = K_N$ we know by Proposition 2.1 that $W \ge \lfloor \frac{N^2-\epsilon}{4C} \rfloor$, where $\epsilon = 1$ when $N$ is odd and 0 otherwise, and we have $E = \frac{N(N-1)}{2}$.

To obtain accurate lower bounds we need to bound the value of $|E_w|$ for a graph with $|V_w| = p$ vertices, satisfying the load constraint. Let $\gamma(C, p)$ be this maximum number of edges. Equations 2 and 3 becomes

$$\sum_{p=2}^{N} a_p \ge \left\lfloor \frac{N^2 - \epsilon}{4C} \right\rfloor \qquad (4)$$

$$\sum_{p=2}^{N} a_p \gamma(C, p) \ge \frac{N(N-1)}{2} \qquad (5)$$

In what follows we will restrict ourselves to the case $C = 2$, which is already non immediate and for which we have been able to obtain exact values. To obtain the right lower bounds when $N$ is even, we need to determine $\gamma(2, p, 2h)$ which is the maximum number of edges of a graph $B$ with $p$ vertices with at least $2h$ vertices of odd degree and such that $L(B, e) \ge 2$ for each edge of $P_N$. Note that $\gamma(2, p) = \gamma(2, p, 0)$.

We will denote by $G+H$ the graph obtained by merging the right most node of $G$ with the left most node of $H$.
**Lemma 4.1** $\gamma(2, p, 2h) = \lfloor \frac{3p-3-h}{2} \rfloor$

**Proof:** We prove the lemma by induction. It is true for $p = 2$ as a graph with two vertices has at most one edge. In that case $h = 1$ and we have equality. For $p = 3$ the maximum number of edges is 3, obtained with a $K_3$, and there is equality for $h = 0$. With $h = 2$, the graph has at most 2 edges and the equality is attained with a $P_3$. Similarly for $p = 4$, the graph has at most 4 edges. Let the vertices be $\{a, b, c, d\}$ with $a < b < c < d$. For $h = 0$ the equality is obtained by the graph $C_4$ consisting of the 4 edges $\{a, b\}, \{b, c\}, \{c, d\}$ and $\{a, d\}$, and for $h = 1$ equality is attained by the graph consisting of an edge joined by a vertex to a $K_3$ more precisely the 4 edges $\{a, b\}, \{b, c\}, \{c, d\}$ and $\{b, d\}$.

Now consider a graph $B$ with $p$ vertices and $2h$ vertices of odd degree. Let $m(B)$ be the number of edges of $B$, and let $u_0$ be the first vertex (in the order of the path).

1. If $u_0$ has degree 1, $B - \{u_0\}$ has at least $2h - 2$ vertices of degree 1 and therefore $m(B) \le \gamma(2, p-1, 2h-2) + 1 = \lfloor \frac{3p-3-h}{2} \rfloor$

2. If $u_0$ is of degree 2, let $u_1$ and $u_2$ be the 2 neighbors of $u_0$, with $u_0 < u_1 < u_2$. As $L(B, \{u_1-1, u_1\}) \le 2$ there is no edge $\{u, u_1\}$ with $u < u_1$, and as $L(B, \{u_1, u_1+1\}) \le 2$ there is at most one edge $\{u_1, v\}$ with $v > u_1$.

(a) If there is no edge $\{u_1, v\}$, the graph obtained from $B$ by deleting $u_0$ and $u_1$ has at least $2h - 2$ vertices of odd degree and so $m(B) \le \gamma(2, p-2, 2h-2) = \lfloor \frac{3p-4-h}{2} \rfloor$.

(b) If there is an edge $\{u_1, v_1\}$ 3 subcases can appear.

i. either $v_1 = u_2$ and the graph obtained from $B$ by deleting $u_0$ and $u_1$ (and therefore the $K_3$ $\{u_0, u_1, v_1\}$) has the same number of vertices of odd degree as $B$ and so $m(B) \le \gamma(2, p-2, 2h) = \lfloor \frac{3p-3-h}{2} \rfloor$.

ii. or $v_1 < u_2$. Due to the load constraint there is no edge $\{u, v_1\}$ with $u < v_1$ and at most one edge $\{v_1, v\}$ with $v_1 < v$. The graph obtained from $B$ by deleting $u_0, u_1, v_1$ has at least $2h - 2$ vertices of odd degree and 3 or 4 edges less than $B$. So $m(B) \le \gamma(2, p-3, 2h) = \lfloor \frac{3p-3-h}{2} \rfloor$.

iii. or $v_1 > u_2$ we do the same reasoning by deleting from $B$ the vertices $u_0, u_1, u_2$ and we obtain $m(B) = \lfloor \frac{3p-3-h}{2} \rfloor$.

So in all cases the bound is proved. Furthermore a careful analysis indicates when the bound is attained. An optimal $(p, 2h)$ can be obtained either by adding an edge joined to a vertex of even degree of a $(p-1, 2h-2)$ optimal graph (case 1); or by adding two edges $\{a, b\}$ and $\{a, c\}$ with $a < b < c$, $c$ being a vertex of even degree of an optimal $(p-2, 2h-2)$ graph (case 2.a); or by adding a $K_3$ joined to a vertex of an optimal $(p-2, 2h)$ graph (case 2.b.i); or by adding a $C_4$ joined to a vertex of an optimal $(p-3, 2h)$ graph (careful analysis of case 2.b.iii).

In particular when $p$ is odd and $h = 0$, the optimal graph is unique and consists of a sequence of $K_3$'s sharing two by two a vertex ($K_3 + K_3 + \cdots + K_3$). $\square$

For any $h$, equality is attained with the graph consisting of $K_3$s and $h$ edges merged in the following way $e + K_3 + e + K_3 + \cdots + K_3 + e + K_3 + K_3 + \cdots + K_3$.
**Theorem 4.2** $A(P_N, 2) \geq \lfloor \frac{11N^2-8N-3}{24} \rfloor$ when N is odd, and when N is even $A(P_N, 2) \geq \lfloor \frac{N(N-1)}{3} \rfloor + \lfloor \frac{N^2}{8} \rfloor + \frac{N}{6} \rfloor$.

**Proof:** By Lemma 4.1 we know that $|E_w| \leq \gamma(2, p, 2h) = \frac{3p_w-3-h_w}{2}$ for a $B_w$ with $p_w$ vertices and $2h_w$ vertices with odd degree. So

$$ \sum_{w=1}^{W} |E_w| \leq \sum_{p=2}^{N} \frac{3p-3}{2} a_p - \sum_{w=1}^{W} \frac{h_w}{2} \qquad (6) $$

If N is odd, $\sum_{w=1}^{W} h_w$ can be equal to 0, but when N is even all vertices of $K_N$ being of odd degree, $\sum_{w=1}^{W} 2h_w \geq N$. So Equations 1, 4 and 5 becomes

$$ A = \sum_{p=2}^{N} pa_p \qquad (7) $$

$$ \sum_{p=2}^{N} a_p \geq \left\lfloor \frac{N^2 - \epsilon}{8} \right\rfloor \qquad (8) $$

$$ \sum_{p=2}^{N} \frac{3p-3}{2} a_p - (1-\epsilon) \frac{N}{4} \geq \frac{N(N-1)}{2} \qquad (9) $$

Thus Equation 9 become

$$ \sum_{p=2}^{N} 3pa_p \geq N(N-1) + 3 \sum_{p=2}^{N} a_p + (1-\epsilon) \frac{N}{2} \qquad (10) $$

$$ A(P_N, 2) \geq \frac{N(N-1)}{3} + \left\lfloor \frac{N^2 - \epsilon}{8} \right\rfloor + (1-\epsilon) \frac{N}{6} \qquad (11) $$

When N is odd, we have $\epsilon = 1$ and so $A(P_N, 2) \geq \frac{11N^2-8N-3}{24}$, and when N is even, we have $\epsilon = 0$ and so $A(P_N, 2) \geq \lfloor \frac{N(N-1)}{3} \rfloor + \lfloor \frac{N^2}{8} \rfloor + \frac{N}{6} \rfloor$ $\square$

# 5 Constructions for $C=2$

## 5.1 3-GDD

Let $v_1, v_2, \dots, v_l$ be non negative integers; the complete multipartite graph with group sizes $v_1, v_2, \dots, v_l$ is defined to be the graph with vertex set $V_1 \cup V_2 \cup \dots \cup V_l$ where $|V_i| = v_i$, and two vertices $u \in V_i$ and $v \in V_j$ are adjacent if $i \neq j$. Using terminology of Design Theory, the graph of type $p_1^{\alpha_1} p_2^{\alpha_2} \dots p_l^{\alpha_l}$ will be the complete multipartite graph with $\alpha_i$ groups of size $p_i$. The existence of a partition of this multipartite graph into $K_k$ is equivalent to the existence of a k-GDD (Group Divisible Design) of type $p_1^{\alpha_1} p_2^{\alpha_2} \dots p_l^{\alpha_l}$.

Here we are interested in the existence of 3-GDD's, that is partitions into $K_3$'s.
**Theorem 5.1 (Existence of a 3-GDD (see [7]))** There exists a 3-GDD of type $p_1^{\alpha_1} p_2^{\alpha_2} \dots p_l^{\alpha_l}$ if and only if (i) each node of the complete multipartite graph has even degree, and (ii) the number of edges is a multiple of 3.

It follows that when $N \equiv 1$ or $3$ (mod 6), $K_N$ can always be partitioned into $K_3$. Various constructions are explained in [21]. One can found in [7] a collection of multipartite graphs for which there exists a 3-GDD.

## 5.2 Constructions for small values of $N$

We have reported in the following table the number of ADMs and the number of subgraphs of optimal constructions for some small cases. The most important constructions are given in Section A.

<table><tr><td>$N$</td><td>2</td><td>3</td><td>4</td><td>5</td><td>6</td><td>7</td><td>8</td><td>9</td><td>10</td><td>11</td><td>12</td><td>13</td><td>16</td><td>17</td><td>20</td></tr><tr><td>$A(P_N, 2)$</td><td>2</td><td>5</td><td>7</td><td>10</td><td>16</td><td>20</td><td>28</td><td>34</td><td>45</td><td>52</td><td>64</td><td>73</td><td>115</td><td>127</td><td>180</td></tr><tr><td>Nb subgraphs</td><td>1</td><td>1</td><td>2</td><td>3</td><td>6</td><td>6</td><td>8</td><td>10</td><td>13</td><td>15</td><td>18</td><td>20</td><td>32</td><td>36</td><td>50</td></tr></table>

## 5.3 Constructions for odd values

In this section we will show that the lower bound is attained for odd values and we will prove it by induction. Note that to have equality, an optimal solution has to contain the minimum number of subgraphs, that is $\lfloor \frac{N^2-1}{8} \rfloor$. If $N \equiv 1$ or $3$ (mod 6), any subgraph of the decomposition with $p$ nodes has exactly $\frac{3p-3}{2}$ edges, which implies $p$ odd and no vertices of odd degree. So the subgraphs of the decomposition are of the form $K_3 + K_3 + \dots + K_3$. If $N \equiv 5$ (mod 6), an optimal decomposition consists of $K_3$'s and one $C_4$, some of them being merged together.

**Theorem 5.2 (1.26 page 190 of [7])** Let $u$ and $v$ be positive integer with $v \le u$. Then a 3-GDD of type $u^1v^11^u$ exists if and only if $(u, v) = (1, 1), (3, 1), (3, 3), (3, 5), (5, 1) \pmod{6, 6}$.

**Corollary 5.3** Given $u$ and $v$ satisfying the condition of Theorem 5.2 and an optimal construction for both $u$ and $v$, we can build an optimal construction for $N = 2u + v$.

**Proof:** Let the nodes of $K_N$ be numbered from left to right $0, 1, \dots, u-1, u, \dots, u+v-1, \dots, 2u+v-1 = N$ and let $A = \{0, 1, \dots, u-1\}, B = \{u, u+1, \dots, u+v-1\}$ and $C = \{u+v, u+v+1, \dots, 2u+v-1\}$.

The 3-GDD of type $u^1v^11^u$ has $\frac{3u^2-u+4uv}{6} K_3$, and we say that the $K_3$s are of type ABC or ACC or CCC depending of their number of nodes in $A$, $B$ and $C$. There are $uv K_3$ of type ABC, $\frac{u(u-v)}{2} K_3$ of type ACC and $\frac{u(v-1)}{6} K_3$ of type CCC.

Note that as expected the number of subgraphs in the partition is $\frac{u^2-1}{8} + \frac{3u^2-u+4uv}{6} - \frac{u(v-1)}{6} = \frac{(2u+v)^2-1}{8}$.

Each node of $A$ is the left most node of $v + \frac{u-v}{2} = \frac{u+v}{2} K_3$ of type ABC or ACC. Since each node of $A$ is the right most node of at most $\frac{u-1}{2}$ subgraphs of the partition of $K_u$, we can merge each subgraph with one $K_3$ and so we save $\frac{u^2-1}{8}$ ADMs.

Each node of $C$ is the right most node of $v K_3$ of type ABC. It is also involved in $u - v K_3$ of type ACC and in $\frac{u-1-(u-v)}{2} = \frac{v-1}{2} K_3$ of type CCC. Thus we can merge each $K_3$ of type CCC with a $K_3$ of type ABC and so we save $\frac{u(v-1)}{6}$ more ADMs.
Note that since each node of $\mathcal{B}$ is the middle node of a $K_3$ of type $\{a, b, c\}$, we can not merge the subgraphs of the partition of $K_v$.

Finally, the construction use $\frac{3u^2-u+4uv}{2} + A(P_u, 2) - \frac{u^2-1}{8} - \frac{u(v-1)}{6} + A(P_v, 2) = \frac{3u^2-u+4uv}{2} + \frac{11u^2-8u-3}{24} - \frac{u^2-1}{8} - \frac{u(v-1)}{6} + \frac{11v^2-8v-3}{24} = \frac{11(2u+v)^2-8(2u+v)-3}{24}$, which is the lower bound. $\square$

**Theorem 5.4** *When $N$ is odd, $A(P_N, 2) = \lfloor \frac{11N^2-8N-3}{24} \rfloor$. Furthermore, the construction contains $\frac{N^2-1}{8}$ subgraphs.*

**Proof:** For $N = 3, 5, 7, 13, 17$ we give direct constructions in Lemmas A.1, A.3, A.4, A.7 and A.9. For other values we will use Corollary 5.3 using induction on $u$.

* When $N = 12t + 1, t \ge 2$, let $u = 6t - 3$ and $v = 7$. Since $(6t - 3, 7) \equiv (3, 1) \pmod{6, 6}$, we can use Corollary 5.3.

* When $N = 12t + 3, t \ge 0$, we can use Corollary 5.3 with $u = 6t + 1$ and $v = 1$

* When $N = 12t + 5, t \ge 3$, we can use Corollary 5.3 with $u = 6t - 3$ and $v = 11$, and for $N = 29$ we can use Corollary 5.3 with $u = 11$ and $v = 7$

* When $N = 12t + 7, t \ge 0$, we can use Corollary 5.3 with $u = 6t + 3$ and $v = 1$

* When $N = 12t + 9, t \ge 0$, we can use Corollary 5.3 with $u = 6t + 3$ and $v = 3$.

* When $N = 12t + 11, t \ge 1$, we can use Corollary 5.3 with $u = 6t + 3$ and $v = 5$. Finally, we can also use Corollary 5.3 for $N = 11$ with $u = 5$ and $v = 1$.

$\square$

## 5.4 Construction for even values

In view of the lower bound, an optimal partition will have exactly $\lfloor \frac{N^2}{8} \rfloor$ subgraphs and each vertex will appear with odd degree and otherwise the value $\frac{3p-3}{2}$ is attained. So we will have mainly $K_3$'s, plus $\frac{N}{2}$ graphs $K_3+e$ (except for some congruence classes where one edge is isolated) some of these $K_3$'s or $K_3+e$ being merged together.

**Lemma 5.5** *There exists a 3-GDD of type $(2u)^1(2v)^1 2^u$ when $u \ge v \ge 1$ and $u(v-1) \equiv 0 \pmod 3$.*

**Proof:** To prove that, one has to check that all nodes have even degree (which is true) and that the total number of edges is a multiple of 3.

Since we have $4u^2+4uv+4uv+4\frac{u(u-1)}{2} = 6u^2+6uv+2u(v-1)$ edges it remains to check that $u(v-1) \equiv 0 \pmod 3$. $\square$

**Theorem 5.6** *When $N$ is even, $A(P_N, 2) = \lfloor \frac{N(N-1)}{3} + \lfloor \frac{N^2}{8} \rfloor + \frac{N}{6} \rfloor = \frac{11N^2-4N}{24} + \epsilon_N$, where $\epsilon_N = \frac{1}{2}$ when $N \equiv 2 \text{ or } 6 \pmod{12}$, $\epsilon_N = \frac{1}{3}$ when $N \equiv 4 \pmod{12}$, $\epsilon_N = \frac{5}{6}$ when $N \equiv 10 \pmod{12}$, and $0$ when $N \equiv 0 \text{ or } 8 \pmod{6}$. Furthermore, the construction contains $\lfloor \frac{N^2}{8} \rfloor$ subgraphs.*
**Proof:** First of all, we know from Lemmas A.1, A.2, A.5, A.6, A.8 and A.10 that the theorem is true for $N = 2, 4, 8, 12, 16, 20$.

Now suppose that the result is true for $2u$ and $2v$, that is for $w = u$ or $v$,

$$A(P_{2w}, 2) = \left\lfloor \frac{2w(2w-1)}{3} + \left\lfloor \frac{4w^2}{8} \right\rfloor + \frac{2w}{6} \right\rfloor = \frac{44w^2 - 4w}{24} + \epsilon_w \quad (12)$$

where $\epsilon_w = \frac{1}{2}$ when $2w \equiv 2$ or $6$ (mod $12$), $\epsilon_w = \frac{1}{3}$ when $2w \equiv 4$ (mod $12$), $\epsilon_w = \frac{5}{6}$ when $2w \equiv 10$ (mod $12$), and $0$ otherwise. Furthermore, the construction use $\left\lfloor \frac{4w^2}{8} \right\rfloor$ subgraphs.

Let now $N = 4u + 2v$, where $u$ and $v$ are such that there exists a 3-GDD of type $(2u)^1(2v)^{12^u}$. Let also the nodes be $A, B, C_1, C_2, \dots, C_u$ with $|A| = 2u$, $|B| = 2v$ and $|C_i| = 2, 1 \le i \le u$, and let $C = \cup_{i=1}^u C_i$.

To simplify the notation, we say that an edge is of type $CC$ if it has one node in $C_i$ and another in $C_j$ with $i \neq j$.

The 3-GDD of type $(2u)^1(2v)^{12^u}$ has $\frac{6u^2-2u+8uv}{3}$ $K_3$: $4uv$ of type $ABC$, $\frac{2u(2u-2v)}{2} = 2u(u-v)$ of type $ACC$ and $\frac{2u(v-1)}{3}$ of type $CCC$.

We observe that each node of $C$ is the right most node of $2v$ $K_3$ of type $ABC$ and is involved in $2u - 2v$ $K_3$ of type $ACC$ and $\frac{2u-2-(2u-2v)}{2} = v - 1$ $K_3$ of type $CCC$. Thus, we can merge each $K_3$ of type $CCC$ with a $K_3$ of type $ABC$ and so save $\frac{2u(v-1)}{3}$ ADMs. Furthermore, we can merge each edge $\{c_i^1, c_i^2\}$ such that $c_i^1, c_i^2 \in C_i, 1 \le i \le u$, with a $K_3$ of type $ABC$ or $ACC$ and so save $u$ more ADMs.

Each node of $A$ is the left most node of $2v + \frac{2u-2v}{2} = u + v$ $K_3$ of type $ABC$ or $ACC$ and is the right most node of at most $\frac{2u-2}{2} + 1 = u$ subgraphs of the optimal construction for $2u$. Thus we can merge each subgraph and save $\left\lfloor \frac{4u^2}{8} \right\rfloor$ more ADMs.

By hypothesis we have

$$A(P_{2u}, 2) - \left\lfloor \frac{4u^2}{8} \right\rfloor = \left\lfloor \frac{2u(2u-1)}{3} + \frac{2u}{6} \right\rfloor = \left\lfloor \frac{u(4u-1)}{3} \right\rfloor = \frac{u(4u-1)}{3} + \alpha_u \quad (13)$$

where $\alpha_u = \frac{1}{3}$ when $u \equiv 2$ (mod 3) and 0 otherwise.

Altogether the construction uses the following number of ADMs.

$$A(P_N, 2) \le A(P_{2u}, 2) - \left\lfloor \frac{4u^2}{8} \right\rfloor + A(P_{2v}, 2) + (6u^2 - 2u + 8uv) - \frac{2u(v-1)}{3} + 2u - u \quad (14)$$

$$\le \frac{u(4u-1)}{3} + \alpha_u + \frac{44v^2 - 8v}{24} + \epsilon_v + \frac{18u^2 - u + 22uv}{3} \quad (15)$$

$$\le \frac{11(4u + 2v)^2 - 4(4u + 2v)}{24} + \alpha_u + \epsilon_v \quad (16)$$

Now we have to check that $\alpha_u + \epsilon_v = \epsilon_N$ in all cases. For that, observe that the conditions of Lemma 5.5 are satisfied when $v = 1$ and when $v = 4$, assuming that $u \ge v \ge 1$. So we have reported in the following table all cases that satisfies the above construction.
<table><thead><tr><th>N</th><th>condition</th><th>u</th><th>v</th><th>α<sub>u</sub></th><th>ε<sub>v</sub></th><th>α<sub>u</sub> + ε<sub>v</sub></th><th>ε<sub>N</sub></th></tr></thead><tbody><tr><td>12t + 2</td><td>t ≥ 1</td><td>3t</td><td>1</td><td>0</td><td><sup>1</sup>&frasl;<sub>2</sub></td><td><sup>1</sup>&frasl;<sub>2</sub></td><td><sup>1</sup>&frasl;<sub>2</sub></td></tr><tr><td>12t + 4</td><td>t ≥ 2</td><td>3t - 1</td><td>4</td><td><sup>1</sup>&frasl;<sub>3</sub></td><td>0</td><td><sup>1</sup>&frasl;<sub>3</sub></td><td><sup>1</sup>&frasl;<sub>3</sub></td></tr><tr><td>12t + 6</td><td>t ≥ 0</td><td>3t + 1</td><td>1</td><td>0</td><td><sup>1</sup>&frasl;<sub>2</sub></td><td><sup>1</sup>&frasl;<sub>2</sub></td><td><sup>1</sup>&frasl;<sub>2</sub></td></tr><tr><td>12t + 8</td><td>t ≥ 2</td><td>3t</td><td>4</td><td>0</td><td>0</td><td>0</td><td>0</td></tr><tr><td>12t + 10</td><td>t ≥ 0</td><td>3t + 2</td><td>1</td><td><sup>1</sup>&frasl;<sub>3</sub></td><td><sup>1</sup>&frasl;<sub>2</sub></td><td><sup>5</sup>&frasl;<sub>6</sub></td><td><sup>5</sup>&frasl;<sub>6</sub></td></tr><tr><td>12t + 12</td><td>t ≥ 1</td><td>3t + 1</td><td>4</td><td>0</td><td>0</td><td>0</td><td>0</td></tr></tbody></table>

Furthermore, the number of subgraphs in our construction for $N = 4u + 2v$ is equal to the number of $K_3$ of type *ABC* plus the number of $K_3$ of type *ACC* and plus the number of subgraphs in the construction for $2v$, that is $4uv + 2u(u - v) + \lfloor \frac{4v^2}{8} \rfloor = \lfloor \frac{(4u+2v)^2}{8} \rfloor$.

In conclusion, Theorem 5.6 is true for all even $N$.

□

## Acknowledgments

Many thanks to C.J. Colbourn for his help in solving the case $N = 17$.

## References

[1] B. Beauquier, J-C. Bermond, L. Gargano, P. Hell, S. Pérennes, and U. Vaccaro. Graph problems arising from wavelength-routing in all-optical networks. In *IEEE Workshop on Optics and Computer Science*, Geneva, Switzerland, April 1997.

[2] J-C. Bermond and S. Ceroi. Minimizing SONET ADMs in unidirectional WDM ring with grooming ratio 3. *Networks*, 41(2), February 2003.

[3] J.-C. Bermond, C.J. Colbourn, A. Ling, and M.-L. Yu. Grooming in unidirectional rings : $K_4 - e$ designs. *Discrete Mathematics*, *Lindner's Volume*, 284(1-3):57-62, 2004.

[4] J-C. Bermond and D. Coudert. Traffic grooming in unidirectional WDM ring networks using design theory. In *IEEE ICC*, Anchorage, Alaska, May 2003.

[5] J-C. Bermond, D. Coudert, and X. Muñoz. Traffic grooming in unidirectional WDM ring networks: the all-to-all unitary case. In *IFIP ONDM*, pages 1135-1153, February 2003.

[6] A. L. Chiu and E. H. Modiano. Traffic grooming algorithms for reducing electronic multiplexing costs in WDM ring networks. *IEEE/OSA Journal of Lightwave Technology*, 18(1):2-12, January 2000.

[7] C.J. Colbourn and J.H. Dinitz, editors. *The CRC handbook of Combinatorial designs*. CRC Press, 1996.

[8] D. Coudert and H. Rivano. Lightpath assignment for multifibers WDM optical networks with wavelength translators. In *IEEE Globecom*, Taipei, Taiwan, November 2002.

[9] D Dor and M. Tarse. Graph decomposition is NP-complete: a complete proof of Holyer's conjecture. *SIAM Journal on Computing*, 26(4):1166-1187, 1997.

[10] R. Dutta, S. Huang, and N. Rouskas. On optimal traffic grooming in elemental network topologies. In *Opticomm*, pages 13-24, Dallas, October 2003.
[11] R. Dutta and N. Rouskas. A survey of virtual topology design algorithms for wavelength routed optical networks. *Optical Networks*, 1(1):73–89, January 2000.

[12] R. Dutta and N. Rouskas. On optimal traffic grooming in WDM rings. *IEEE Journal of Selected Areas in Communications*, 20(1):1–12, January 2002.

[13] R. Dutta and N. Rouskas. Traffic grooming in WDM networks: Past and future. *IEEE Network*, 16(6):46–56, November/December 2002.

[14] L. Epstein and A. Levin. Better bounds for minimizing sonet adms. In *WAOA*, September 2004.

[15] O. Gerstel, P. Lin, and G. Sasaki. Wavelength assignment in a WDM ring to minimize cost of embedded SONET rings. In *IEEE Infocom*, pages 94–101, San Francisco, California, 1998.

[16] O. Gerstel, R. Ramaswani, and G. Sasaki. Cost-effective traffic grooming in WDM rings. *IEEE/ACM Transactions on Networking*, 8(5):618–630, 2000.

[17] O. Goldschmidt, D. Hochbaum, A. Levin, and E. Olinick. The SONET edge-partition problem. *Networks*, 41(1):13–23, 2003.

[18] I. Holyer. The NP-completeness of some edge-partition problems. *SIAM Journal on Computing*, 10(4):713–717, 1981.

[19] J.Q. Hu. Optimal traffic grooming for wavelength-division-multiplexing rings with all-to-all uniform traffic. *OSA Journal of Optical Networks*, 1(1):32–42, 2002.

[20] J.Q. Hu. Traffic grooming in wdm ring networks: A linear programming solution. *OSA Journal of Optical Networks*, 1(11):397–408, 2002.

[21] C.C. Lindner and C.A. Rodger. *Design Theory*. CRC Press, 1997. ISBN 0849339863.

[22] E. Modiano and P. Lin. Traffic grooming in WDM networks. *IEEE Communications Magazine*, 39(7):124–129, July 2001.

[23] M. Shalom and S. Zaks. A $10/7+\epsilon$ approximation for minimizing the number of adms in sonet rings. In *IEEE BroadNets*, pages 254–262, October 2004.

[24] A. Somani. Survivable traffic grooming in WDM networks. In D.K. Gautam, editor, *Broad band optical fiber communications technology – BBOFCT*, pages 17–45, Jalgaon, India, December 2001. Nirtali Prakashan. Invited paper.

[25] P.-J. Wan, G. Calinescu, L. Liu, and O. Frieder. Grooming of arbitrary traffic in SONET/WDM BLSRs. *IEEE Journal of Selected Areas in Communications*, 18(10):1995–2003, October 2000.

[26] J. Wang, W. Cho, V. Vemuri, and B. Mukherjee. Improved approaches for cost-effective traffic grooming in WDM ring networks: Ilp formulations and single-hop and multihop connections. *IEEE/OSA Journal of Lightwave Technology*, 19(11):1645–1653, November 2001.

[27] X. Yuan and A. Fulay. Wavelength assignment to minimize the number of SONET ADMs in WDM rings. In *IEEE ICC*, New York, April 2002.

[28] X. Zhang and C. Qiao. An effective and comprehensive approach for traffic grooming and wavelength assignment in SONET/WDM rings. *IEEE/ACM Transactions on Networking*, 8(5):608–617, 2000.
A Small cases

Remark that all the subgraphs that we consider in the constructions satisfies $L(B_w, e) \le 2$. It
is clear for a $K_3 \{u, v, w\}$ where we suppose $u < v < w$. For an edge $\{t, u\}$ glued with the $K_3$
$\{u, v, w\}$, we suppose that $t < u < v < w$.

**Lemma A.1** $A(P_2, 2) = 2$ and $A(P_3, 2) = 3$.

**Lemma A.2** $A(P_4, 2) = 7$.

**Proof:** Let the vertices of $P_4$ be $\mathbb{Z}_4$. The first subgraph contains the $K_3 \{1, 2, 3\}$ plus the edge $\{0, 1\}$, and the second subgraph contains the two edges $\{0, 2\}$ and $\{0, 3\}$. $\square$

**Lemma A.3** $A(P_5, 2) = 10$.

**Proof:** Let the vertices of $P_5$ be $\mathbb{Z}_5$. The graphs of the decomposition are the $2 K_3 \{0, 2, 4\}$ and $\{0, 1, 3\}$ plus the subgraph $B_3$ containing the $4$ edges $\{1, 2\}$, $\{2, 3\}$, $\{3, 4\}$ and $\{1, 4\}$. This construction fit the lower bound. $\square$

**Lemma A.4** $A(P_7, 2) = 20$

**Proof:** Let the vertices of $P_7$ be $\mathbb{Z}_7$, that is $0, 1, 2, 3, 4, 5, 6$. The construction is obtained using the partition of $K_7$ into the $7 K_3 \{i, i+1, i+3\}$, indices being taken modulo $7$, and the remark that the $2 K_3 \{0, 1, 3\}$ and $\{3, 4, 6\}$ fit in a same subgraph. This construction use 20 ADMs and according to Theorem 4.2 we have $A(P_7, 2) \ge 20$. $\square$

**Lemma A.5** $A(P_8, 2) = 28$

**Proof:** Let the nodes be $a_1, a_2, b_1, b_2, c_1, c_2, d_1, d_2$. We have 4 groups of 2 consecutive nodes and we use a 3-GDD of type $2^4$. Our construction consist on the $4 K_3 \{a_2, b_2, c_2\}, \{b_1, c_2, d_1\}, \{a_1, c_2, d_2\}$ and $\{a_1, b_2, d_1\}$ plus the $4 K_3 + e \{a_1, a_2\} + \{a_2, b_1, d_2\}, \{b_1, b_2\} + \{b_2, c_1, d_2\}, \{a_1, b_1, c_1\} + \{c_1, c_2\}$ and $\{a_2, c_1, d_1\} + \{d_1, d_2\}$. This construction use 28 ADMs. $\square$

**Lemma A.6** $A(P_{12}, 2) = 64$

**Proof:** Let the nodes of $P_{12}$ be $a_1, a_2, b_1, b_2, c_1, c_2, d_1, d_2, e_1, e_2, f_1, f_2$ and arrange them in this order.

Our construction consist on the 2 subgraphs (union of $K_3$) $\{a_1, b_1, c_1\}+\{c_1, e_2, f_1\}$ and $\{a_2, c_1, d_2\}+\{d_2, e_1, f_2\}$, plus the $6 K_3 + e \{a_1, a_2\} + \{a_2, b_2, f_1\}, \{b_1, b_2\} + \{b_2, c_2, d_2\}, \{c_1, c_2\} + \{c_1, d_1, e_1\}, \{a_2, c_2, d_1\}+\{d_1, d_2\}, \{a_2, b_1, e_1\}+\{e_1, e_2\}$ and $\{a_1, d_2, f_1\}+\{f_1, f_2\}$, and plus the $10 K_3 \{b_1, d_1, f_1\}, \{b_2, d_1, e_2\}, \{a_1, c_2, e_2\}, \{b_1, c_2, f_2\}, \{a_1, d_1, f_2\}, \{b_2, c_1, f_2\}, \{a_1, b_2, e_1\}, \{b_1, d_2, e_2\}, \{c_2, e_1, f_1\}$ and $\{a_2, e_2, f_2\}$. Altogether, we use $2 \times 5 + 6 \times 4 + 10 \times 3 = 64$ ADMs. $\square$

**Lemma A.7** $A(P_{13}, 2) = 73$

**Proof:** Let the vertices of $P_{13}$ be $\mathbb{Z}_{13}$ and remark that $K_{13}$ can be partitioned into the $26 K_3 \{i, i+1, i+4\}$ and $\{i, i+5, i+7\}$, $i \in \mathbb{Z}_{13}$. Our construction consist on the subgraph $\{0, 1, 4\} + \{4, 5, 8\} + \{8, 9, 12\}$, plus the $3$ subgraphs $\{i, i+1, i+4\} + \{i+4, i+5, i+8\}$, $i = 1, 2, 3$, plus the $4 K_3 \{j, j+1, j+4\}$, $j = 9, 10, 11, 12$, and plus the $13 K_3 \{k, k+5, k+7\}$, $k \in \mathbb{Z}_{13}$. Altogether this construction use $7+3 \times 5+17 \times 3 = 73$ ADMs and according to Theorem 4.2 we have $A(P_{13}, 2) \ge 73$. $\square$

<figure><img src="image_3.png" /></figure>
**Lemma A.8** $A(P_{16}, 2) = 115$

**Proof:** Let the vertices of $P_{16}$ be $A \cup B \cup C$, where $A = \{a_0, a_1, a_2, a_3, a_4, a_5\}$, $B = \{b_0, b_1, b_2, b_3\}$ and $C = \{c_0, c_1, c_2, c_3, c_4, c_5\}$. Our construction is based on the existence of a 3-GDD of type $6^14^{12}3$, which consist on 24 $K_3$ of type $ABC$, 6 $K_3$ of type $ACC$ and 2 $K_3$ of type $CCC$, and by merging the 5 subgraphs of the decomposition of $K_6$ with $K_3$s of type $ABC$, the 2 $K_3$ of type $CCC$ and the 3 edges $\{c_i, c_{i+1}\}$, $i = 0, 1, 2$, with $K_3$s of type $ABC$. Altogether this construction use 115 ADMs and the subgraphs of the decomposition are:

* The 4 graphs on 5 vertices $\{a_0, b_0, c_1\} + \{c_1, c_2, c_4\}$, $\{a_2, b_1, c_0\} + \{c_0, c_3, c_4\}$, $\{a_0, a_2, a_5\} + \{a_5, b_1, c_1\}$ and $\{a_1, a_3, a_5\} + \{a_5, b_2, c_2\}$, so 20 ADMs.

* The $4 K_3 + e \{a_2, b_3, c_0\} + \{c_0, c_1\}$, $\{a_1, b_0, c_2\} + \{c_2, c_3\}$, $\{a_0, b_2, c_4\} + \{c_4, c_5\}$ and $\{a_2, a_3\} + \{a_3, b_0, c_5\}$, so 16 ADMs

* The 2 graphs on 6 vertices $(2K_3 + e) \{a_0, a_3, a_4\} + \{a_4, a_5\} + \{a_5, b_0, c_4\}$ and $\{a_0, a_1\} + \{a_1, a_2, a_4\} + \{a_4, b_0, c_0\}$, so 12 ADMs,

* The $21 K_3 \{a_0, b_1, c_3\}$, $\{a_0, b_3, c_5\}$, $\{a_1, b_1, c_4\}$, $\{a_1, b_2, c_1\}$, $\{a_1, b_3, c_3\}$, $\{a_2, b_0, c_3\}$, $\{a_2, b_2, c_3\}$, $\{a_3, b_1, c_5\}$, $\{a_3, b_2, c_5\}$, $\{a_3, b_3, c_4\}$, $\{a_4, b_1, c_2\}$, $\{a_4, b_2, c_0\}$, $\{a_4, b_3, c_2\}$, $\{a_5, b_3, c_1\}$, $\{a_0, c_0, c_2\}$, $\{a_1, c_0, c_5\}$, $\{a_2, c_2, c_5\}$, $\{a_3, c_1, c_3\}$, $\{a_4, c_1, c_5\}$, $\{a_5, c_3, c_5\}$ and $\{b_0, b_2, b_3\}$, so 63 ADMs

* The star $\{b_0, b_1\} + \{b_1, b_2\} + \{b_1, b_3\}$, so 4 ADMs.

□

**Lemma A.9** $A(P_{17}, 2) = 127$

**Proof:** Let the vertices of $P_{17}$ be $\mathbb{Z}_{17}$. The decomposition is based on the existence of a 3-GDD of type $3^{25}1^32^3$ (which was kindly given to us by C.J. Colbourn) and the subgraphs are:

* The 9 graphs on 5 vertices (consisting of two $K_3$s with a common vertex, the one in the middle) $\{0, 1, 2\} + \{2, 5, 11\}$, $\{3, 4, 5\} + \{5, 13, 15\}$, $\{1, 4, 11\} + \{11, 12, 13\}$, $\{2, 4, 14\} + \{14, 15, 16\}$, $\{0, 5, 6\} + \{6, 11, 14\}$, $\{2, 3, 7\} + \{7, 11, 16\}$, $\{0, 4, 8\} + \{8, 11, 15\}$, $\{1, 5, 9\} + \{9, 13, 14\}$ and $\{0, 3, 10\} + \{10, 12, 14\}$, so altogether 45 ADMs.

* The 24 $K_3$s $\{4, 6, 12\}$, $\{1, 6, 13\}$, $\{2, 6, 15\}$, $\{3, 6, 16\}$ $\{1, 7, 12\}$, $\{4, 7, 13\}$, $\{3, 7, 15\}$, $\{0, 7, 14\}$ $\{2, 8, 12\}$, $\{3, 8, 13\}$, $\{1, 8, 16\}$, $\{5, 8, 14\}$ $\{3, 9, 12\}$, $\{4, 9, 15\}$, $\{2, 9, 16\}$, $\{0, 9, 11\}$ $\{2, 10, 13\}$, $\{1, 10, 15\}$, $\{4, 10, 16\}$, $\{5, 10, 11\}$ $\{1, 3, 14\}$, $\{0, 12, 15\}$, $\{0, 13, 16\}$ and $\{5, 12, 16\}$, so 72 ADMs.

* The 3 graphs decomposing the $K_5$ on $6, 7, 8, 9, 10$, the $2 K_3 \{6, 8, 10\}$ and $\{6, 7, 9\}$ and the $C_4 \{7, 8, 9, 10\}$, so 10 more ADMs.

In summary our construction use 127 ADMs, the lower bound.

□

**Lemma A.10** $A(P_{20}, 2) = 180$

**Proof:** The construction is similar to the construction of Lemma A.8 and use a 3-GDD of type $2^38^{12}3^3$. □