Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6423680 | Electronic Notes in Discrete Mathematics | 2016 | 6 Pages |
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 Siâ (v) be the set of vertices at distance i from v. We show that |Siâ(v)|=diâaiâ1diâ1ââ¯âa1dâa0, where d is the degree of the digraph and the coefficients akâ{0,1} are explicitly calculated. Analogously, let w be a vertex adjacent from v such that Siâ(v)â©Sjâ(w)â â for some j. We prove that |Siâ(v)â©Sjâ(w)|=diâbiâ1diâ1ââ¦âb1dâb0, where the coefficients btâ{0,1} are determined from the coefficients ak of the polynomial expression of |Siâ(v)|. An application to deflection routing in De Bruijn and Kautz networks serves as motivation for our study. It is worth-mentioning that our analysis can be extended to other families of digraphs on alphabet or to general iterated line digraphs.