×

Restricted arc-connectivity of generalized de Bruijn digraphs and Kautz digraphs. (English) Zbl 1474.05231

Summary: The restricted arc-connectivity of a digraph is an important parameter to measure fault-tolerance of interconnection networks. This paper determines that the restricted arc-connectivity of the de Bruijn digraph \({B_G} (n, d)\) is equal to \(2d - 2\) for diameter \(k \ge 4\) and \(d \ge 4\), and the restricted arc-connectivity of Kautz digraph \({K_G} (n, d)\) is equal to \(2d - 2\) for \(k \ge 4\), \(d \ge 4\) or \(d \ge 3\), \(k \ge 5\), \(g.c.d (n, d) \ge 2\) and \(n\) is divisible by \((d + 1)\). As consequences, the super restricted arc-connectivity of \({B_G} (n, d)\) and \({K_G} (n, d)\) is obtained immediately. This paper shows that \({\lambda_h} (D) \le \min \{{\xi^h} (D), |{V_1}|\lambda ({D_2}), |{V_2}|\lambda ({D_1})\}\). In particular, for diameter \(k \ge 4\), it can be determined that \({\lambda_2} ({B_G} (n, d) \times {B_G} (n, d)) = 4d - 2\) for \(d \ge 3\) and \({\lambda_2} ({K_G} (n, d) \times {K_G} (n, d)) = 4d - 2\) for \(d \ge 2\).

MSC:

05C40 Connectivity
05C20 Directed graphs (digraphs), tournaments
Full Text: DOI