1 Introduction

We follow the terminology and notation (Bang-Jensen and Gutin 2001) for digraphs. A digraph is simple if it does not contain loops and parallel arcs. For a digraph \(D=(V(D),A(D))\), let V(D) and A(D) denote the vertex set and arc set of D, respectively. Let e(D) denote the size |A(D)| of the digraph D. Two vertices are called adjacent if they are connected by an arc. If there is an arc from vertex u to vertex v, we indicate this by writing uv, call u and v the tail and the head of uv, respectively. For \(A, B\subseteq V(D)\), (A, B) denotes all the arcs of D with their tails in A and with their heads in B, and \([A,B]=(A, B)\cup (B, A)\). The complete digraph \(\overrightarrow{K_n}\) of order n is the simple digraph in which every pair of vertices are joined by two opposite arcs. A digraph D is strongly connected (or a strong digraph) if for every pair \(x, \ y \in V(D)\), there exists a directed path from x to y and a directed path from y to x. For a strong digraph D, a set \(S\subset V\) is a separator (or a separating set) if \(D-S\) is not strongly connected. A digraph D is k-strongly connected if \(|V|\ge k+1\) and D has no separator with less than k vertices. The largest k such that D is k-strongly connected is the vertex connectivity of D, denoted by \(\kappa (D)\). Similarly, the arc connectivity of D, denoted by \({\lambda (D)}\), is the minimum number of arcs whose deletion make the resulting new digraph not strongly connected. For a strong digraph D, a vertex \(u\in V(D)\) is called a cut vertex if \(D-u\) is not strongly connected. The distance from vertex x to vertex y in D, denoted by d(x, y), is the minimum length of a (x, y)-path. The eccentricity ecc(v) of a vertex \(v\in V(D)\) is \(\max \{d(v, x)|\ x\in V(G)\}\). The diameter of a digraph D, denoted by \(\mathrm{diam}(D)\), is the maximum eccentricity of a vertex in G.

For undirected graphs, Vizing (1965) determined the maximum number of edges in a graph with a given domination number. Dankelmann et al. (2004) determined the maximum size of graphs with given independence number and total domination number. The maximum size of undirected graphs with given some parameters are well treated in the literature, see Sanchis (1991) and Sanchis (2000). For some recent results on various properties of digraphs, we refer to Bang-Jensen and Nielsen (2008), Broersma and Li (2002), Dankelmann (2015), Ferneyhough et al. (2002), Huang and Zhan (2011), Liu et al. (2010) and Severini (2006). Up to now, there are few articles about the maximum size of digraphs with given parameters.

In Sect. 2, we characterize the maximum size of strong digraphs under the constraint that the number of cut vertices are fixed, and characterize the extremal digraphs. In addition, the maximum sizes of strong digraphs are determined when connectivity or arc connectivity is fixed. In Sect. 3, we establish the Nordhaus–Gaddum type theorem for diameter of digraphs when \(\overrightarrow{K_n}\) decomposing into many parts. We also pose a related conjecture on Wiener index of digraphs.

2 Maximum size of digraphs with given cut vertices

A strongly connected digraph that has no cut vertices is called a block. A block is called a complete block if it is a complete digraph. We denote by \({\mathcal {T}}_{n,k}\) the set of strong digraphs with n vertices and k cut vertices. So, \({\mathcal {T}}_{n,0}\) simply denotes the all strong digraphs with no cut vertices.

First recall that the following two elementary results (see Bondy and Murty (1976), p.173) on digraphs.

Lemma 2.1

If D is a digraph of order n with no directed cycle, then there is an ordering \(v_1,\ldots , v_n\) of V(D) such that, for \(1\le i\le n\), every arc of D with head \(v_i\) has its tail in \(\{v_1,\ldots , v_{i-1}\}\).

Lemma 2.2

Let \(D_1,\ldots , D_m\) be all strong components of a digraph D. The condensation W of D is a directed graph with m vertices \(w_1,\ldots , w_m\); there is an arc in W with tail \(w_i\) and head \(w_j\) if and only if there is an arc in D with tail in \(D_i\) and head in \(D_j\). Then the condensation W of D contains no directed cycle.

Corollary 2.3

Let D be a strongly connected digraph with vertex connectivity \(k>0\). Suppose that S is a k-vertex cut of D and \(D_1,\ldots , D_s\) are the strong components of \(D-S\). Then there exists a permutation p of \(1,\ldots , s\) such that, for any \(v\in V(D_{p(i)})\), every arc with head v has its tail in \(D_{p(1)}\cup \cdots \cup D_{p(i)}\).

Proof

It is an immediate consequence of Lemmas 2.1 and 2.2. \(\square \)

Corollary 2.4

Let D be a digraph and let \(B_1,\ldots , B_s\) be all blocks of D. Then there exists a permutation p of \(1,\ldots , s\) such that, for any \(v\in V(B_{p(i)})\), every arc with head v has its tail in \(B_{p(1)}\cup \cdots \cup B_{p(i)}\).

Proof

Let B be a digraph with vertices \(b_1,\ldots , b_s\), in which there is an arc \(b_ib_j\) if and only if either \(V(B_i)\cap V(B_j)=\emptyset \) and there exists an arc with its tail in \(V(B_i)\) and with its head in \(V(B_j)\), or \(V(B_i)\cap V(B_j)\ne \emptyset \), there exists an arc with its tail in \(V(B_i)\setminus V(B_j)\ne \emptyset \) and with its head in \(V(B_j)\setminus V(B_i)\). It is easy to see that B does not contain a directed cycle. By Lemma 2.1, there is a permutation p of \(1,\ldots , s\) such that, every arc of B with head \(b_{p(i)}\) has its tail in \(\{b_{p(1)},\ldots , b_{p(i-1)}\}\). This permutation is the one we desired. \(\square \)

Lemma 2.5

Let n be a positive integer and \(D\in {\mathcal {T}}_{n,0}\). If D has the maximum size among \({\mathcal {T}}_{n,k}\), then for any minimum vertex cut S of D, \(D-S\) has exactly two strong components, and both of them are complete.

Proof

Let \(D_1,\ldots , D_s\) be a specified ordering of all the strong components of \(D-S\), with the property as given Corollary 2.3. If \(s\ge 3\), then adding an arc \(v_jv_i\) with \(v_i\in V(D_i)\), \(v_j\in V(D_j)\) and \(2\le i<j\le s\) to D results in a new digraph \(D'\), which has the same connectivity as D does. Hence, \(s=2\). Moreover, both \(D_1\) and \(D_2\) are complete, otherwise, it contradicts the maximality of D. \(\square \)

Let \(D_1\) and \(D_2\) be two vertex-disjoint digraphs. The join \(D_1\bigtriangledown D_2\) of \(D_1\) and \(D_2\) is the digraph with vertex set \(V(D_1)\cup V(D_2)\) and arc set \(A(D)=A(D_1)\cup A(D_2)\cup \{uv, vu|\ u\in V(D_1), v \in V(D_2)\}\). Let \(T_{s,n-t-s}^t\) denote the digraph \(K_t\bigtriangledown (K_s \cup K_{n-t-s})\cup E\), where \(E=\{xy|\ x\in K_s, y\in K_{n-t-s}\}\).

Theorem 2.6

Let D be a strongly connected digraph with \(\kappa (D)=t\) for an integer \(t\ge 2\). Then \(e(D)\le n^2-2n+t+1\), equality holds if and only if \(D\cong T_{1,n-t-1}^{t}\) or \(T_{n-t-1,1}^{t}\).

Proof

Let \(t\ge 2\) be an integer. Suppose that D is a digraph the maximum size among all strongly connected graphs with connectivity t. By Lemma 2.5, we have \(D-S\) contains exactly two strongly connected components, say, \(D_1\) and \(D_2\). Furthermore, either \(D\cong T_{s,n-t-s}^{t}\) or \(D\cong T_{n-t-s,s}^{t}\), where \(0< s<n-t\). We show that \(|V(D_1)|=1\) or \(|V(D_2)|=1\). To show this, we may assume that \(D\cong T_{s,n-t-s}^{t}\) and \(s=|V(D_1)|\ge |V(D_2)|=n-t-s\ge 2\).

Let \(D'\cong T_{s+1,n-t-s-1}^{t}\). But

$$\begin{aligned} e(D')= & {} e(D)-(|V(D_2)|-1)+(|V(D_2)|-1)|V(D_1)|\\= & {} e(D)+(|V(D_2)|-1)(|V(D_1)|-1)\\> & {} e(D), \end{aligned}$$

which contradicts the choice of D. So, \(|V(D_1)|=1\) or \(|V(D_2)|=1\), which implies \(D\cong T_{1,n-t-1}^{t}\) or \(T_{n-t-1,1}^{t}\). It is routine to check that

$$\begin{aligned} e(T_{1,n-t-1}^{t})=e(T_{n-t-1,1}^{t})=n(n-1)-(n-t-1)=n^2-2n+t+1. \end{aligned}$$

The proof is completed. \(\square \)

Let n and k be two positive integers with \(n\ge k+1\). Let \(n_1,\ldots , n_{k+1}\) be integers with \(n_1+\cdots +n_{k+1}=n+k\). Define a digraph, denoted by \(T(n_1,\ldots , T_{k+1})\), as follows: it is composed of \(k+1\) complete blocks \(B_1,\ldots , B_{k+1}\) with \(|V(B_i)|=n_i\) for each \(i=1,\ldots , k+1\), and \(|V(B_i)\cap V(B_{i+1})|=1\) for each \(i=1,\ldots , k\), in which there is an arc xy if and only if \(x, y \in V(B_i)\) for an integer \(i\in \{1,\ldots k+1\}\), or \(x\in V(B_i), y \in V(B_j)\) for \(1\le i<j\le k+1\). It is clear that \(T(n_1,\ldots , n_{k+1})\in {\mathcal {T}}_{n,k}\).

Lemma 2.7

Let n and k be two integers with \(n>k>0\). If \(D\in {\mathcal {T}}_{n,k}\) is a digraph with maximum size in \({\mathcal {T}}_{n,k}\), then

  1. (1)

    each block is complete,

  2. (2)

    each cut vertex is contained in exactly two blocks of D, and

  3. (3)

    each block contains at most two cut vertices.

Proof

(1) is trivial, since if there is a block B which is not complete, adding those missing arcs to B results in a new digraph \(D'\in {\mathcal {T}}_{n,k}\), a contradiction.

To prove (2), let v be a cut vertex, and let \(B_1,\ldots , B_t\) be all blocks of D, containing v, where \(t\ge 3\). Since each \(B_i\) is strongly connected, By Corollary 2.4, without loss of generality, we may assume that \(B_1,\ldots , B_t\) be an ordering such that for any arc \(xy\in A(D)\), if \(x\in V(B_i)\), \(y\in V(B_j)\) then \(i\le j\). Let \(D'\) be a digraph obtained from D by replacing \(D[V(B_2)\cup \cdots V(B_t)]\) with the complete block on \(V(B_2)\cup \cdots \cup V(B_t)\). It is clear that \(D'\in {\mathcal {T}}_{n,k}\). It contradicts the maximality of D.

Now we prove (3). Since \(D\in {\mathcal {T}}_{n,k}\), it follows from (2) that there are exactly \(k+1\) blocks in D. Let \(B_1,\ldots , B_{k+1}\) be the ordering of all blocks of D, as specified in Corollary 2.4, and let \(n_i=|V(B_i)|\) for any \(i\in \{1,\ldots , k+1\}\). By contradiction, suppose that \(B_p\) is a block of D contains three cut vertices, say \(u_r, u_s, u_t\), and let \(u_r=V(B_p)\cap V(B_r)\), \(u_s=V(B_p)\cap V(B_s)\), \(u_r=V(B_p)\cap V(B_t)\), where \(r<s<t\). One can see that either \((V(B_r), B(B_s))=\emptyset \) or \((V(B_s), B(B_t))=\emptyset \), otherwise, \(u_s\) will not be a cut vertex. However, \(e(T(n_1,\ldots , n_{k+1}))>e(D)\), which contradicts the choice of D. \(\square \)

Theorem 2.8

If \(D\in {\mathcal {T}}_{n,k}\), then \(e(D)\le n^2-(k+1)n+\frac{k(k+3)}{2}\), with equality if and only if \(D\cong T(n_1,\ldots , n_{k+1}))\), where \(n_1+\cdots + n_{k+1}=n+k\), and \(n_j=2\) for all \(j\ne i\) for some \(i\in \{1,\ldots , k+1\}\).

Proof

Let D be a digraph in \({\mathcal {T}}_{n,k}\) with the maximum size. The proof of (3) of Theorem 3.7 indicates that \(D\cong T(n_1,\ldots , n_{k+1}))\), where \(n_1,\ldots , n_{k+1}\) are \(k+1\) integers at least two with \(n_1+\cdots + n_{k+1}=n\).

We claim that \(n_j=2\) for all \(j\ne i\) for some \(i\in \{1,\ldots , k+1\}\). Otherwise, let \(n_r\ge 3\) and \(n_s\ge 3\) for some \(1\le r<s\le k+1\). Without loss of generality, we may further assume that \(n_r\le n_s\). Let \(D'=T(m_1,\ldots , m_{k+1})\) with \(m_r=n_r-1\), \(m_s=n_s+1\), and \(m_j=n_j\) for all \(j\in \{1,\ldots , k+1\}\setminus \{r, s\}\).

Obviously, \(e(D')=e(D)+2(n_s-n_r+1)>e(D)\). This is a contradiction. It follows that at most one of \(D_1,\ldots ,D_{k+1}\) has order greater than 2, and thus \(D\cong T(n_1,\ldots , n_{k+1})\), where \(n_1+\cdots + n_{k+1}=n+k\), and \(n_j=2\) for all \(j\ne i\) for some \(i\in \{1,\ldots , k+1\}\). For such a digraph D, one can easily obtain

$$\begin{aligned} e(D)=n(n-1)-\sum _{t=2}^{k+1}(n-t)=n^2-(k+1)n+\frac{k(k+3)}{2}. \end{aligned}$$

The proof is completed. \(\square \)

Theorem 2.9

Let D be a strongly connected digraph with \(\eta (D)=t\) for an integer \(t\ge 2\). Then \(e(D)\le n^2-2n+t+1\), equality holds if and only if \(D\cong T_{1,n-t-1}^{t}\) or \(T_{n-t-1,1}^{t}\).

Proof

Suppose that D is a digraph with the maximum size among all strong digraphs with arc connectivity t. Let S be an arc cut of D with \(|S|=t\), and let \(D_1\), \(D_2\) be the two strong components of \(D-S\). The maximality of D assures that exactly one of the following holds:

  1. (1)

    for every \(u\in V(D_1)\) and \(v\in V(D_2)\), \(uv\in A(D)\);

  2. (2)

    for every \(u\in V(D_1)\) and \(v\in V(D_2)\), \(vu\in A(D)\).

Without loss of generality, (1) holds. Therefore

$$\begin{aligned} e(D)=n(n-1)-(n_1n_2-t)=n(n-1)-n_1(n-n_1)+t, \end{aligned}$$

where \(n_i=|V_i|\) for \(i=1, 2\). It is easy to see that \(n_1=1\) or \(n_1=n-1\) since e(D) has the maximum size. If \(n_1=1\), then \(D\cong T_{1,n-t-1}^{t}\), and if \(n_1=n-t-1\), then \(D\cong T_{n-t-1,1}^{t}\). \(\square \)

3 Decomposition, diameter and Wiener index

For a positive integer k, a k-decomposition \((G_1,\ldots , G_k)\) of a graph G is a partition of its edge set to form k spanning subgraphs \(G_1,\ldots , G_k\). That is, each \(G_i\) has the same vertices as G, and every edge of G belongs to exactly one of \(G_1,\ldots , G_k\). For a graph parameter p, a positive integer k, and a graph G, to determine the extremal (maximum or minimum) values of

$$\begin{aligned} \left\{ \sum _{i=1}^k p(G_i): (G_1, G_2,\ldots , G_k)\ { is}\ { a} \ { decomposition}\ { of}\ { G}\right\} \end{aligned}$$

is a fundamental problem in graph theory. The particular case when \(G=K_n\) attracts many attentions on various graph parameters (Füredi et al. 2005; Goddard et al. 1992; Zhang and Wu 2005). Nordhaus and Gaddum (1956) first initiate such kind of research on chromatic number of graphs for the case when \(k=2\) and \(G=K_n\), and proved that

$$\begin{aligned} 2\sqrt{n}\le \chi (H)+\chi (\bar{H})\le n+1 \end{aligned}$$

for any graph H of order n.

Assume a graph G is connected. The distance \(d_G(u,v)\) of two vertices u and v is the length of a shortest path connecting them in G. The diameter diam(G) of G is \(\max \{d_G(u,v): u, v\in V(G)\}\). Xu (1991) proved that for a connected graph G with the connected complement \(\bar{G}\),

$$\begin{aligned} 4\le { diam}(G)+{ diam}(\bar{G})\le n+1, \end{aligned}$$

when the order n of G is at least five. Xu’s result is recently extended in An et al. (2011) as follows.

Theorem 3.1

(An et al. 2011) Let \(K_n\) be the complete graph of order n and \(k\ge 2\) for any fixed integer. Assume \((G_1, G_2,\ldots , G_k)\) is a k-decomposition of \(K_n\) such that \(G_{i}\) is connected for each \(i=1,\ldots ,k\). Then any sufficiently large n (with respect to k),

$$\begin{aligned} 2k\le \sum _{i=1}^{k}{ diam}(G_{i})\le (k-1)(n-1)+2. \end{aligned}$$

We establish the directed analogue of Theorem 4.1. A k-decomposition of \((D_1, D_2,\ldots , D_k)\) of a digraph of D is a partition of its arc set to form k spanning subdigraphs \(D_1,\ldots , D_k\). That is, each \(D_i\) has the same vertices as D, and every arc of D belongs to exactly one of \(D_1,\ldots , D_k\). Recall that the complete digraph \(\overrightarrow{K_n}\) is the digraph of order n, in which every pair of vertices are joined by two arcs with opposite directions.

Theorem 3.2

Let \(\overrightarrow{K_n}\) be the complete graph of order n and \(k\ge 2\) for any fixed integer. Assume \((D_1, D_2,\ldots , D_k)\) is a k-decomposition of \(\overrightarrow{K_n}\) such that \(D_i\) is strongly connected for each \(i=1,\ldots , k\). Then for any sufficiently large n (with respect to k),

$$\begin{aligned} 2k\le \sum _{i=1}^{k}diam(D_i)\le (n-1)k. \end{aligned}$$

Note that a strongly connected non-complete digraph has diameter at least 2. Then the lower bound of the above theorem is derived from the following theorem.

Theorem 3.3

Let \(k\ge 2\) be any fixed integer. For any sufficiently large n (with respect to k), there is a k-decomposition \((D_1, D_2,\ldots , D_k)\) of \(\overrightarrow{K_n}\) with \(diam(D_{i})=2\) for each \(i=1,\ldots , k\).

Proof

We prove it by the probabilistic argument, which is similar to the proof of Theorem 1.2 of An et al. (2011). Color each arc of \(\overrightarrow{K_n}\) by colors \(1, 2,\ldots , k\), randomly and independently, with the equal probability \(p=\frac{1}{k}\). For each i, \(1\le i\le m\), \(D_i\) denotes the spanning subgraph of \(\overrightarrow{K_n}\) with the arc set \(A_i\), the set of arcs with the color i. Hence \((D_1, D_2,\ldots , D_k)\) is a decomposition of \(\overrightarrow{K_n}\). Let \(E_i\) be the event that \(diam(D_i)\le 2\). Then \(\cap _{i=1}^kE_i\) is the event that \(diam(D_i)=2\) for every \(i=1, 2,\ldots , k\). For any ordered pair of distinct vertices (u, v) of \(V(\overrightarrow{K_n})\), let \(B_i(u, v)\) be the event that \(d_{D_i}(u,v)> 2\). So,

$$\begin{aligned} E_i=\cap _{(u,v)}\overline{B_i(u, v)}. \end{aligned}$$

Since \(Pr(B_i(u,v))=(1-p)(1-p^2)^{n-2}\), we have

$$\begin{aligned} Pr(E_i)= & {} Pr(\cap _{(u, v)}\overline{B_i(u, v)})\\= & {} 1-Pr(\cup _{(u, v)}{B_i(u, v)})\\\ge & {} 1-\sum _{(u, v)}Pr(B_i(u, v))\\= & {} 1-n(n-1)(1-p)(1-p^2)^{n-2} \end{aligned}$$

Since \(p=\frac{1}{k}<1\), \(n(n-1)(1-p)(1-p^2)^{n-2}\rightarrow 0\) as \(n \rightarrow \infty \), and \(Pr(E_i)\rightarrow 1\) as \(n\rightarrow \infty \). It follows that \(Pr(E_i\cup E_j)\rightarrow 1, Pr(E_i\cup E_j\cup E_l)\rightarrow 1,\ldots , Pr(E_1\cup E_2\cup \cdots \cup E_k)\rightarrow 1\) as \(n \rightarrow \infty \). By the principle of inclusion-exclusion,

$$\begin{aligned} Pr(\cap _{i=1}^kE_i)= & {} \sum _{i=1}^k Pr(E_i)-\sum _{i<j} Pr(E_i\cup E_j)+\cdots +(-1)^{k-1}Pr(\cup _{i=1}^kE_i)\\&\rightarrow k-\big (^k_2\big )+\cdots +(-1)^{k-1}\big (^k_k\big )=1>0. \end{aligned}$$

It follows that there is a k-decomposition \((D_1, D_2,\ldots , D_k)\) of \(\overrightarrow{K_n}\) with \(diam(D_{i})=2\) for each \(i=1,\ldots , k\). \(\square \)

The upper bound of Theorem 3.2 is the consequence of the following Lemma 3.4. To prove it, recall a well-known result for the decomposition of complete graphs. If n is even, then \(K_n\) can be decomposed into \(n-1\) perfect matchings. If n is odd, then \(K_n\) can be decomposed into \(\frac{n-1}{2}\) hamiltonian cycles.

Lemma 3.4

Let \(\overrightarrow{K_n}\) be the complete graph of order n. For any fixed integer k with \(2\le k\le 2\lfloor \frac{n}{2}\rfloor \) there is a k-decomposition \((D_1, D_2,\ldots , D_k)\) of \(\overrightarrow{K}_n\) such that \(diam(D_{i})=n-1\) for each \(i=1,\ldots , k\).

Proof

Let \(C_1, C_2,\ldots , C_{k-1}\) be \(k-1\) edge-disjoint hamiltonian cycles of \(K_n\). Without loss of generality, we may assume that \(E(C_{k-1})=\{v_1v_2, v_2v_3,\ldots , v_{n-1}v_n, v_nv_{1}\}\) by abusing our notation. Let \(\overrightarrow{C_i}\) be a directed cycle of \(\overrightarrow{K_n}\) as an orientation of \(C_i\) for each \(i=1,\ldots , k-2\), and let \(\overrightarrow{C}_{k-1}\) be the orientation of \(C_{k-1}\) with arcs \(v_iv_{i+1}\) for each \(i=1,\ldots n-1\) and \(v_nv_1\), and \(\overrightarrow{C_k}\) be the directed cycle obtained from \(\overrightarrow{C}_{k-1}\) with all arcs reversed. Let \(A'=A(\overrightarrow{K}_n)-\bigcup _{i=1}^{k}A(C_i)\) and let \(A'_1 , A'_2\) be the partition of \(A'\) such that \(A'_1=\{v_iv_j|i>j\}\) and \(A'_2=\{v_iv_j|i<j\}\). Set \(D_i= \overrightarrow{C_i}\) if \(i\le k-2\), and \(D_{k-1}=\overrightarrow{C}_{k-1}\cup A_1'\) and \(D_{k}=\overrightarrow{C_k}\cup A_2'\). It is trivial to see that \((D_1, D_2,\ldots , D_k)\) be a k-decomposition of \(\overrightarrow{K_n}\) with \(diam(D_i)=n-1\) for all i. \(\square \)

The Wiener index W(G) of a connected graph G is the sum of distance of all pairs of vertices in G, that is,

$$\begin{aligned} W(G)=\sum _{u, v\in V(G)} d_G(u, v). \end{aligned}$$

It is one of most widely studied topological indices in mathematical chemistry, see a survey (Dobrynin et al. 2001) and some recent works (Balakrishnan et al. 2008; Bereg and Wang 2007; Eliasi and Taeri 2009; Li et al. 2011; Wagner et al. 2009). Zhang and Wu (2005) showed that for any \(n\ge 5\) and 2-decomposition \((G_1, G_2)\) of \(K_n\), if \(G_1\) and \(G_2\) are connected, then

$$\begin{aligned} \frac{3}{2}n(n-1)\le W(G_1)+W(G_2)\le \frac{n^3-n}{6}+\left( ^n_2\right) +n-1. \end{aligned}$$

Motivated from the aboe result, the authors Li et al. (2011) posed the following conjecture and verified its validity for \(k=3\).

Conjecture 1

(Li et al. 2011) Let \(K_n\) be the complete graph of order n and \(k\ge 2\) any fixed integer. Assume that \((G_1, G_2,\ldots , G_k)\) is a k-decomposition of \(K_n\) such that \(G_i\) is connected for each \(i=1, 2,\ldots , k\). Then for any sufficiently large n with respect to k,

$$\begin{aligned} (2k-1)\left( ^n_2\right) \le \sum _{i=1}^{k}W(G_{i})\le (k-1)\frac{n^3-n}{6}+\left( ^n_2\right) +(k-1)(n-1). \end{aligned}$$

The lower bound is trivial and is attained by any k-decomposition \((G_1, G_2,\ldots , G_k)\) of \(K_n\) with \(diam(G_i)=2\) for each \(i=1, 2,\ldots , k\). In this decomposition,

$$\begin{aligned} W(G_i)=e(G_i)+2\left( \left( ^n_2\right) -e(G_i)\right) =2\left( ^n_2\right) -e(G_i), \ and \ \sum _{i=1}^k e(G_i)=\left( ^n_2\right) \!, \end{aligned}$$

thus \(\sum _{i=1}^{k}W(G_{i})=(2k-1)\left( ^n_2\right) \). If the conjecture is true, the upper bound is attained by a decomposition \((G_1, G_2,\ldots , G_k)\) of \(K_n\) with \(G_i\cong P_n\) for \(k-1\) \(i'\)s. Without loss of generality, let \(G_i\cong P_n\) for \(i=1, 2,\ldots , k-1\). Then \(diam(G_k)=2\) for any sufficiently large n, and thus \(\sum _{i=1}^{k}W(G_{i})=(k-1)\frac{n^3-n}{6}+\left( ^n_2\right) +(k-1)(n-1)\).

Now we pose the directed version of Conjecture 1 as follows.

Conjecture 2

Let \(k\ge 2\) be a fixed integer and assume that \((D_1, D_2,\ldots , D_k)\) is a k-decomposition of \(\overrightarrow{K_n}\) such that \(D_i\) is strongly connected for each \(i=1, 2,\ldots , k\). Then for any sufficiently large n with respect to k,

$$\begin{aligned} (2k-1)n(n-1)\le \sum _{i=1}^{k}W(D_{i})\le (k-1)\frac{n^3-n^2}{2}+n(n+k-2). \end{aligned}$$

Indeed, the lower bound of the above conjecture is true, which is attained by any k-decomposition \((D_1, D_2,\ldots , D_k)\) of \(\overrightarrow{K_n}\) with \(diam(D_i)=2\) for each \(i=1, 2,\ldots , k\). Since

$$\begin{aligned} W(D_i)= & {} a(D_i)+2\left( n(n-1)-a(D_i)\right) \\= & {} 2n(n-1)-a(D_i), \ and \ \sum _{i=1}^k a(D_i)=n(n-1), \end{aligned}$$

thus \(\sum _{i=1}^{k}W(D_{i})=(2k-1)\left( ^n_2\right) \). If the upper bound is true, it is attained by a decomposition \((D_1,\ldots , D_k)\) of \(\overrightarrow{K_n}\), in which \(D_i=\overrightarrow{C_i}\) for all \(i\in \{1,\ldots , k-1\}\).