LINE DIGRAPH ITERATIONS AND CONNECTIVITY ANALYSIS OF DEBRUIJN AND KAUTZ GRAPHS

A graph has spread (m, k, l) if for any m + 1 distinct nodes x, y1, ... , y(m) and m positive integers r1, ... , r(m) such that SIGMA(i)r(i) = k, there exist k node-disjoint paths of length at most l from x to the y(i), where r(i) of them end at y(i). This concept contains, and is related to, many important concepts used in communications and graph theory. In this paper, we prove an optimal general theorem about the spreads of digraphs generated by line digraph iterations. Useful graphs, like the de Bruijn and Kautz digraphs, can be thus generated. Then we apply the theorem to the de Bruijn and Kautz digraphs to derive optimal bounds on their spreads, which implies previous results and resolves open questions on their connectivity, diameter, k-diameter, vulnerability, and some other measures related to length-bound disjoint paths.