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 i s 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 graph s, 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 opt imal bounds on their spreads, which implies previous results and resol ves open questions on their connectivity, diameter, k-diameter, vulner ability, and some other measures related to length-bound disjoint path s.