We initiate a study of the toughness of directed graphs by considering the natural generalization of that for ordinary graphs. After providing some general results, computations are completed for a few natural examples. Maximum possible toughness is also considered. Some open problems are posed.
The toughness of a graph [1,2,6,7] is a measure of its vulnerability to vertex removal. If the links between nodes in a network always reflect two-way connections, then the toughness of the corresponding graph measures how well the network can withstand node losses. However, if the network has links that are only one-way, then an appropriate directed graph needs to be considered.
We shall refer to a directed graph as a digraph and only consider simple digraphs. These are defined on a set of vertices with a set of arcs, each of which has the form \((u,v)\). The ordinary graphs we consider, however, may have multiple edges. Throughout this article, strong connectivity for a digraph is taken as the analog of connectivity for an ordinary graph. That is, vertices \(u\) and \(v\) in a digraph \(G\) are in the same component if there exists both a path from \(u\) to \(v\) and a path from \(v\) to \(u\) in \(G\). Thus, throughout, the modifier ‘strong’ is dropped in reference to connectivity and components.
For each digraph \(G\), let \(\kappa(G)\) denote the connectivity for \(G\). Given a set of vertices \(U\) in a digraph \(G\), the number of components in the subgraph of \(G\) induced by \(U\) is denoted by \(\omega(U)\). A separating set for \(G\) is a set \(S\) of vertices of \(G\) such that \(\omega(G \setminus S) > 1\). We extend Chvátal’s definition [2] of the toughness of an ordinary graph and allow \(G\) to be a digraph by \[\tau(G) = \min \left\{ \frac{|S|}{\omega(G \setminus S)} : \text{$S$ is a separating set for $G$} \right\}.\]
A tough-set for \(G\) is a separating set \(S\) for which \(\tau(G) = {|S|}/{\omega (G \setminus S)}\). All standard notation and terminology not presented here can be found in [8].
There will be no ambiguity in using the same parameter names for both the categories of ordinary graphs and digraphs, as the context will always be clear. Moreover, we consider the following two constructs for moving between these categories. Given a simple ordinary graph \(G\), let \(G^*\) be the digraph on the same vertex set with two arcs \((u,v)\) and \((v,u)\) for each edge \(\{u,v\}\). Conversely, given a digraph \(G\), its underlying graph \(\underline{G}\) is the ordinary graph (not necessarily simple) with an edge \(\{u,v\}\) for each arc \((u,v)\). An arc \((u,v)\) in a digraph is said to be reversible if \((v,u)\) is also an arc. A digraph is symmetric if every arc is reversible. The following two lemmas are immediate from the definitions.
Lemma 2.1. For any graph \(G\), \(\tau(G^*) = \tau(G)\).
That is, Lemma 2.1 equates the toughness of a symmetric digraph with that of a corresponding ordinary graph. For example, since we know [2] that the toughness of the ordinary cycle \(C_n\) is \(1\), we now have that \(\tau(C_n^*) = 1\) as well.
Lemma 2.2. ] For any digraph \(G\), \(\tau(G) \leq \tau(\underline{G})\). Moreover, if \(G\) is symmetric, then equality holds.
In general, we rarely expect equality to hold in Lemma 2.2 for digraphs that are not symmetric. However, Figure 1 displays a nontrivial example in which equality does hold.
Note there that any vertex serves as a tough set for \(G\), while only the central vertex plays that role for \(\underline{G}\).
The following theorem extends immediately from ordinary graphs to digraphs.
Theorem 2.3. ([2]) For a digraph \(G\), \(\tau(G) \leq {\kappa(G)}/{2}\).
Although equality in Theorem 2.3 holds for the example from Figure 1, equality is unlikely to hold unless the digraph is rich in reversible edges. Thus we consider more typical types of connected digraphs.
For each integer \(n \geq 2\), we take \(\mathbb{Z}_n\) to be the set \(\{1,2,\ldots,n\}\), where addition is taken modulo \(n\). The directed cycle \(C_n\) is the digraph on vertex set \(\mathbb{Z}_n\) with an arc \((i,i+1)\) for each \(i\). The first class of digraphs we consider is a generalization of this construction. For each positive integer \(r < n\), define \(C_n^r\) to be the digraph on vertex set \(\mathbb{Z}_n\) with an arc \((i,i+j)\) for each \(i\) and \(1 \leq j \leq r\). Of course, \(C_n^1 = C_n\). Figure 2 displays the case in which \(n = 12\) and \(r = 2\).
The value of the graphs \(C_n^r\) to us comes principally from their connectivity, which we establish in Theorem 3.2. Much of the work for the proof of that result is done by the following technical lemma.
Lemma 3.1. ] Given any integers \(a \leq b\) and \(1 \leq s \leq r < n\), there exist \(s\) disjoint paths contained in the segment \(\{ a+1, \ldots, b+s \}\) of \(C_n^r\) that join the vertices \(\{ a+1, \ldots, a+s \}\) to the vertices \(\{ b+1, \ldots, b+s \}\).
Proof. We may assume that \(a=0\). By the Division Algorithm, we have \(b+s = qs+d\) for some \(q \geq 1\) and \(0 \leq d < s\). We first join \(\{1,\ldots, s \}\) to \(\{(q-1)s+1,\ldots,qs\}\) by adding \(s\) to each vertex a total of \(q-1\) times. If \(d=0\), then we are done. So assume \(d \geq 1\). It remains for us to join \(\{(q-1)s+1,\ldots,b,b+1,\ldots qs\}\) to \(\{b+1,\ldots,qs, qs+1,\ldots,b+s\}\). This is done by adding \(s\) to each vertex in the intial portion \(\{(q-1)s+1,\ldots,b\}\), which joins it to the final portion \(\{qs+1,\ldots,b+s\}\). ◻
Theorem 3.2. ] For integers \(n\) and \(r\) with \(1 \leq r < n\), \(\kappa(C_n^r) = r\).
Proof. Since \(\{1,\ldots, r\}\) is a disconnecting set of size \(r\), it remains to show that at least \(r\) vertices must be removed to disconnnect \(C_n^r\). By Menger’s Theorem, it suffices to produce \(r\) internally disjoint paths from \(\{n\}\) to \(\{k\}\), for each \(1 \leq k \leq n-1\).
First consider the case in which \(k > r\). By the Division Algorithm, we have \(k-1 = qr+d\) for some \(q \geq 1\) and \(0 \leq d < r\). For each \(1 \leq i \leq r\), we have the arc \((n,i)\). This gives \(r\) internally disjoint paths from \(\{n\}\) to the set \(\{1,\ldots,r\}\). By Lemma 3.1, we can extend these to be internally disjoint paths that reach \(\{k-r,\ldots,k-1\}\). Finally, for each \(r \geq i \geq 1\), we have the arc \((k-i,k)\), and this extends our paths to be \(r\) internally disjoint paths from \(\{n\}\) to \(\{k\}\).
Now consider the case in which \(k \leq r\). We have the arc \((n,k)\), and, for each \(1 \leq i \leq k-1\) we have the path of \((n,i)\) followed by \((i,k)\). Thus we currently have \(k\) internally disjoint paths from \(\{n\}\) to \(\{k\}\). Further, for each \(k+1 \leq i \leq r\), we have the arc \((n,i)\), which gives us \(r-k\) internally disjoint paths from \(\{n\}\) to \(\{k+1,\ldots,r\}\). By Lemma 3.1, we can then extend these to be internally disjoint paths that reach \(\{n-r+k,\ldots,n-1\}\). Finally, for each \(r \geq i \geq k+1\), we have the arc \((n+k-i,k)\), and this extends our paths to be \(r-k\) additional internally disjoint paths from \(\{n\}\) to \(\{k\}\). ◻
Theorem 3.3. For integers \(n\) and \(r\) with \(1 \leq r < n\), \(\tau(C_n^r) = \frac{r}{n-r}\).
Proof. Observe that \(S = \{1,\ldots, r\}\) is a disconnecting set such that every vertex of \(C_n^r \setminus S\) forms an isolated component. Thus, \(\omega(C_n^r \setminus S) = n – r\), and \(\tau(C_n^r) \leq \frac{r}{n-r}\).
Now let \(S\) be any disconnecting set for \(C_n^r\). By Theorem 3.2, \(|S| \geq r\). Of course, \(\omega(C_n^r \setminus S) \leq n – |S| \leq n – r\). Thus, \(\tau(C_n^r) \geq \frac{r}{n-r}\). ◻
Our second class of digraphs references the ordinary complete graph \(K_m\) on \(m\) vertices. Since our construction involves a direct product with \(K_m^*\) it has lots of reversible edges.
Theorem 3.4. ] For integers \(n,m \geq 2\), \(\tau(C_n \times K_m^*) = \frac{m}{n}\).
Proof. Let \(S = \{(1,1)\} \cup \{(2,j) : 2 \leq j \leq m\}\). Observe that \(S\) is a disconnecting set of size \(m\). For each \(1 \leq i \leq n\), there is now a component of the complement of \(S\) contained in the remaining portion of \(\{i\} \times K_m^*\). That is, \(\omega((C_n \times K_m^*) \setminus S) = n\). Thus, \(\tau(C_n \times K_m^*) \leq \frac{m}{n}\).
Now let \(S\) be any disconnecting set. If \(|S| < m\), then there must be some \(1 \leq j \leq m\) such that \(S\) is disjoint from \(C_n \times \{j\}\), whence \(S\) is not a disconnecting set. Thus \(|S| \geq m\). For each \(1 \leq i \leq n\), there can be at most one component of the complement of \(S\) contained in the remaining portion of \(\{i\} \times K_m^*\). Hence \(\omega((C_n \times K_m^*) \setminus S) \leq n\), and we have \(\tau(C_n \times K_m^*) \geq \frac{m}{n}\). ◻
In contrast with Theorem 3.4, it follows from Lemma 2.1 and a result of Chvátal [2] that \[\tau(K_n^* \times K_m^*) = \tau((K_n \times K_m)^*) = \tau(K_n \times K_m) = \frac{n+m-2}{2}.\] Of course, this agrees with Theorem 3.4 when \(n=2\). For our third class of digraphs, we consider the tori, which have no reversible edges.
Theorem 3.5. For each integer \(n \geq m \geq 2\), \(\tau(C_n \times C_m) \leq \frac{m}{n+m^2-2m}\).
Proof. Let \(S = \{(i,m+1-i) : 1 \leq i \leq m \}\). Observe that \(S\) is a disconnecting set of size \(m\). In \((C_n \times C_m) \setminus S\), each vertex \((i,j)\) with \(1 \leq i,j \leq m\) and \(j \neq m+1-i\) forms an isolated component. Further, for each \(m+1 \leq i \leq n\), the subgraph \(\{i\} \times C_m\) forms a component. Thus \[\omega((C_n \times C_m) \setminus S) = m(m-1) + n-m = n+m^2-2m. \] ◻
Since \(K_2^* = C_2\), Theorem 3.4 gives \(\tau(C_n \times C_2) = \frac{2}{n}\), and we thus have equality in Theorem 3.5 when \(m = 2\). In fact, we conjecture equality there for all \(m\). What are some other natural digraphs for which the toughness can be computed?
The determination of the maximum toughness among ordinary graphs with a fixed number of vertices and edges has been studied extensively [3,4,5]. In our consideration of digraphs here, we have encountered, for example, three digraphs with \(9\) vertices and \(18\) arcs. Specifically, we saw that \(\tau(C_9^*) = 1\), \(\tau(C_9^2) = \frac{2}{7}\), and \(\tau(C_3 \times C_3) \leq \frac{1}{2}\). In fact, those values illustrate the following result.
Theorem 4.1. If \(G\) is a digraph on \(n \geq 4\) vertices with \(2n\) arcs, then \(\tau(G) \leq 1\).
Proof. We consider here the ordinary degree of vertices in \(\underline{G}\). Since the sum of the degrees in \(G\) is \(4n\), there must be a vertex \(v\) with \(\deg(v) \leq 4\). Thus we have either \(\text{in-}\!\deg(v) \leq 2\) or \(\text{out-}\!\deg(v) \leq 2\). If \(\text{in-}\!\deg(v) \leq 2\), then take \(S = \{u : (u,v) \text{ is an arc} \}\), and, if \(\text{out-}\!\deg(v) \leq 2\), then take \(S = \{u : (v,u) \text{ is an arc} \}\). In any case, \(|S| \leq 2\), and \(v\) is an isolated vertex in \(G \setminus S\), whence \(\omega(G \setminus S) \geq 2\). Therefore, \(\tau(G) \leq \frac{|S|}{\omega(G \setminus S)} \leq 1\). ◻
Since \(\tau(C_n^*) = 1\), Theorem 4.1 gives that the maximum toughness among digraphs with \(n\) vertices and \(2n\) arcs is \(1\). This leads us to the following conjecture.
Conjecture 4.2. For any \(n \geq 4\) and \(0 \leq m \leq \frac{n(n-1)}{2}\), the maximum toughness among digraphs with \(n\) vertices and \(2m\) arcs equals the maximum toughness among ordinary graphs with \(n\) vertices and \(m\) arcs.
Conjecture 4.2 suggests that the toughest way to build a network in which only one-way links are available is to pair together links to make them reversible.