کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6423680 | 1632577 | 2016 | 6 صفحه PDF | دانلود رایگان |

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.
Journal: Electronic Notes in Discrete Mathematics - Volume 54, October 2016, Pages 157-162