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í, J.; Muñoz, X.
Type of activity
Journal article
Journal
Electronic notes in discrete mathematics
Date of publication
2016-10-17
Volume
54
First page
157
Last page
162
DOI
https://doi.org/10.1016/j.endm.2016.09.028
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
http://hdl.handle.net/2117/103040
URL
http://www.sciencedirect.com/science/article/pii/S1571065316301226
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...
Citation
Fàbrega, J., Martí-Farré, J., Muñoz, X. Layer structure of De Bruijn and Kautz digraphs: an application to deflection routing. "Electronic notes in discrete mathematics", 17 Octubre 2016, vol. 54, p. 157-162.
Keywords
De Bruijn and Kautz digraphs, Deflection routing, General iterated line digraphs
Group of research
COMBGRAPH - Combinatorics, Graph Theory and Applications