Go to the content (press return)

# FUTUR. Website for the scientific production of UPC researchers

## Layer structure of De Bruijn and Kautz digraphs. An application to deflection routing

Author
Fàbrega, J.; Martí-Farré, J.; Muñoz, X.
Type of activity
Presentation of work at congresses
Name of edition
10th Discrete Mathematics Days
Date of publication
2016
Presentation's date
2016-07-08
Book of congress proceedings
Discrete Mathematics Days:10th of the Jornadas de Matemática Discreta y Algorítmica (JMDA): Barcelona, Spain: july 6-8, 2016: booklet of abstracts
First page
38
Last page
39
Project funding
Grup de Qualitat "Combinatoria, Teoría de Grafs i Aplicacions"
Técnicas de Optimización en Teoría de Grafos, Grupos y Combinatoria. Aplicacions a Rdes, Algoritmos y Protocolos de Comunicación
Repository
Abstract
In the main part of this paper we present polynomial expressions for the cardinalities of some sets of interest of the nice distance-layer structure of the well-known De Bruijn and Kautz digraphs. More precisely, given a vertex $v$, let $S_{i}^\star(v)$ be the set of vertices at distance $i$ from $v$. We show that $|S_{i}^\star(v)|=d^i-a_{i-1}d^{i-1}-\cdots -a_{1} d-a_{0}$, where $d$ is the degree of the digraph and the coefficients $a_{k}\in\{0,1\}$ are explicitly calculated. Analogously, l...
Keywords
De Bruijn and Kautz digraphs, Deflection routing., General iterated line digraphs
Group of research
COMBGRAPH - Combinatorics, Graph Theory and Applications