PDF

Line Digraphs and Applications (Miguel Angel Fiol- Universitat Politècnica de Catalunya)

Line digraphs have both nice theoretical properties and interesting applications, mainly in the context of interconnection and communication networks. For instance, iterated line digraphs---such as De Brujin and Kautz digraphs---are among the densest known digraphs, and they have high connectivity, easy routing, efficient broadcasting algorithms, etc. Moreover, line digraphs provide some examples of highly structured digraphs, as some families of weakly distance-regular digraphs--such as some of the Moore-type digraphs and the generalized cycles. Other areas where we can encounter the line digraph structure are group theory (through Cayley digraphs), Fourier analysis (in the FFT implementation), probability theory (through certain Markov chains), just to mention a few.