A note on recursive properties of the de Bruijn, Kautz and FFT digraphs

It is well known that the de Bruijn digraph (and also the Kautz digraph) of in- and out-degree d and diameter n is the line-digraph of the same digraph of diameter n − 1. We show here that the Bruijn digraph of diameter n is the intersection digraph of complete bipartite digraphs of the de Bruijn di...

Full description

Saved in:
Bibliographic Details
Published in:Information processing letters 1995-03, Vol.53 (5), p.255-259
Main Authors: Heydemann, M.C, Sotteau, D
Format: Article
Language:English
Subjects:
Applied sciences
Computer networks
Computer science
control theory
systems
Cycles
de Bruijn
Exact sciences and technology
FFT
Information processing
Information retrieval. Graph
Interconnection networks
Kautz
Mathematical models
Studies
Telecommunications
Telecommunications and information theory
Teleprocessing networks. Isdn
Theoretical computing
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:It is well known that the de Bruijn digraph (and also the Kautz digraph) of in- and out-degree d and diameter n is the line-digraph of the same digraph of diameter n − 1. We show here that the Bruijn digraph of diameter n is the intersection digraph of complete bipartite digraphs of the de Bruijn digraph of diameter n + 1. The same property occurs for Kautz and Fast-Fourier-Transform digraphs.
ISSN:0020-0190
1872-6119
DOI:10.1016/0020-0190(94)00210-P