Search

This is the peer reviewed version of the following article: Fàbrega, J.; Martí, J.; Muñoz, X. Distance-layer structure of the De Bruijn and Kautz digraphs: analysis and application to deflection routing. "Networks", 29 Juliol 2023, which has been published in final form at https://onlinelibrary.wiley.com/doi/10.1002/net.22177. This article may be used for non-commercial purposes in accordance with Wiley Terms and Conditions for Use of Self-Archived Versions. This article may not be enhanced, enriched or otherwise transformed into a derivative work, without express permission from Wiley or by statutory rights under applicable legislation. Copyright notices must not be removed, obscured or modified. The article must be linked to Wiley’s version of record on Wiley Online Library and any embedding, framing or otherwise making available the article or pages thereof by third parties from platforms, services and websites other than Wiley Online Library must be prohibited., In this article, we present a detailed study of the reach distance-layer structure of the De Bruijn and Kautz digraphs, and we apply our analysis to the performance evaluation of deflection routing in De Bruijn and Kautz networks. Concerning the distance-layer structure, we provide explicit polynomial expressions, in terms of the degree of the digraph, for the cardinalities of some relevant sets of this structure. Regarding the application to defection routing, and as a consequence of our polynomial description of the distance-layer structure, we formulate explicit expressions, in terms of the degree of the digraph, for some probabilities of interest in the analysis of this type of routing. De Bruijn and Kautz digraphs are fundamental examples of digraphs on alphabet and iterated line digraphs. If the topology of the network under consideration corresponds to a digraph of this type, we can perform, in principle, a similar vertex layer description., Partially supported by the Ministerio de Ciencia e Innovación/Agencia Estatal de Investigación, Spain, and the European Regional Development Fund under project PGC2018-095471-B-I00; and by AGAUR from the Catalan Government under project 2017SGR-1087., Peer Reviewed, Postprint (author's final draft)

© 2023 Elsevier. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0, Many dissemination processes in graphs can be described as follows at a basic level. At each step of the process, some vertices of the graph are coloured blue, and the remaining are coloured white, and a well-defined infection rule acts locally on a chosen element of the graph. As an outcome of this action, perhaps one or more white vertices are forced to become blue. Zero forcing, power domination and bootstrap percolation are some examples of widely studied infection rules. This paper presents a general view of infection rules on graphs, paying particular attention to monotone rules. We state several results referring to the final stable set of blue vertices at the end of the dissemination process driven by the infection rule , and to the combinatorial transversal relation between the families of inclusion-minimal -forcing and -immune sets of the graph. Our results apply to many infection rules considered in the literature, as well as to new ones introduced in this paper. Besides, for each one of these infection rules, we provide a characterization of their -immune sets formulated in terms of neighbourhood, so without referring to the iterative dissemination process acting on the graph. In the second part of the paper, and for the particular rules treated in the first part ( -PUSH, -PUSH, -PUSH, -PULL, -PULL, and -wPULL), we prove the -Completeness of the decision problem associated to the corresponding -immune number of the graph., Partially supported by the Ministerio de Ciencia e Innovaci´on/Agencia Estatal de Investigaci´on, Spain, and the European Regional Development Fund under project PGC2018- 095471-B-I00; and by AGAUR from the Catalan Government under project 2017SGR–1087., Peer Reviewed, Postprint (published version)