On the Domination Number of 𝑑-Constrained de Bruijn Graphs (Short Paper)⋆ Tiziana Calamoneri1,*,† , Angelo Monti1,† and Blerina Sinaimeri2,† 1 Sapienza University of Rome, Italy 2 Luiss University, Italy Abstract Motivated by the work on the domination number of de Bruijn graphs and some of its generalizations, we introduce a natural generalization of de Bruijn graphs (directed and undirected), namely 𝑑-constrained de Bruijn graphs, where 𝑑 is a positive integer, and then study the domination number of these graphs. Within the definition of 𝑑-constrained de Bruijn graphs, de Bruijn and Kautz graphs correspond to 1-constrained and 2-constrained de Bruijn graphs, respectively. This generalization inherits many structural properties of de Bruijn graphs and may have similar applications in interconnection networks or bioinformatics. We establish upper and lower bounds for the domination number on 𝑑-constrained de Bruijn graphs both in the directed and in the undirected case. These bounds are often very close and in some cases we are able to find the exact value. Keywords domination number, de Bruijn graph, Kautz graph In graph theory, the study of domination and dominating sets plays a prominent role. This topic has been extensively studied for more than 30 years [1, 2] due to its applications in several areas, e.g. wireless networks [3], protein-protein interaction networks [4], social networks [5]. For a comprehensive treatment of domination and its variations, we refer to [2]. In an undirected graph, a vertex dominates itself and all its neighbors. The concept of domination can be naturally transferred to directed graphs, where a vertex dominates itself and all of its outgoing neighbors. A dominating set of a (direct or undirected) graph is a subset 𝑆 of vertices such that every vertex in the graph is dominated by at least one vertex in 𝑆. The domination number of a graph 𝐺 is the minimum cardinality of a dominating set of 𝐺, and is denoted by 𝛾(𝐺). Finding a minimum dominating set for general graphs is widely known to be Proceedings of the 23rd Italian Conference on Theoretical Computer Science, Rome, Italy, September 7-9, 2022 ⋆ Partially supported by the following research projects: Sapienza University of Rome, projects: no. RM120172A3F313FE "Measuring the similarity of biological and medical structures through graph isomorphism", no. RM11916B462574AD "A deep study of phylogenetic tree reconciliations" and no. RM1181642702045E "Comparative Analysis of Phylogenies". * Corresponding author. † These authors contributed equally. " calamo@di.uniroma1.it (T. Calamoneri); monti@di.uniroma1.it (A. Monti); bsinaimeri@luiss.it (B. Sinaimeri) ~ https://sites.google.com/di.uniroma1.it/tiziana-calamoneri/home-page (T. Calamoneri); https://impresaemanagement.luiss.it/docenti/cv/354334 (B. Sinaimeri)  0000-0002-4099-1836 (T. Calamoneri); 0000-0002-3309-8249 (A. Monti); 0000-0002-9797-7592 (B. Sinaimeri) Β© 2022 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). CEUR Workshop Proceedings http://ceur-ws.org ISSN 1613-0073 CEUR Workshop Proceedings (CEUR-WS.org) NP-hard [6] and hence it is a challenge to determine classes of graphs for which 𝛾(𝐺) can be exactly computed. A closed formula for the domination number has been exactly determined only for few specific classes of graphs such as de Bruijn graphs [7], Kautz graphs [8], generalized Petersen graphs [9], Cartesian product of two directed paths [10] and graphs defined by two levels of the 𝑛-cube [11]. Furthermore, close bounds are provided for some generalizations of the previous classes [12, 13]. Here we focus on the well-known de Bruijn graphs which have various applications in different areas as for example bioinformatics [14, 15], interconnection networks [16] and peer- to-peer systems [17]. De Bruijn graphs are defined as follows: Definition 1. Given an alphabet Ξ£ and a positive integer 𝑛, the de Bruijn graph of order 𝑛 on Ξ£ is defined as follows: - vertices are associated to all the sequences (οΈ€ in Σ𝑛 )οΈ€ - edges are the ordered pair of the form (π‘Ž1 , . . . , π‘Žπ‘› ), (π‘Ž2 , . . . , π‘Žπ‘› , π‘Žπ‘›+1 ) , where π‘Ž1 , . . . and π‘Žπ‘›+1 are in Ξ£. In Fig. 2.a we show a de Bruijn graph of order 2 on Ξ£ = {1, 2, 3}. Particular induced subgraphs of de Bruijn graphs have also been studied due to their applications related to both DNA assembly and high-performance or fault-tolerant computing [18]. These subgraphs can be defined by choosing particular subsets of vertices. For instance, the subgraph induced by the sequences of Σ𝑛 that do not contain equal adjacent characters corresponds to the well-known Kautz graph [19] which has many properties that are desirable in computer networks [18, 20]. In Fig. 2.b we show a Kautz graph of order 2 on Ξ£ = {1, 2, 3}. The undirected version of de Bruijn and Kautz graphs can be easily obtained by simply ignoring the direction of the edges and removing loops and multiple edges (see Fig. 2.c as the undirected version of the Kautz graph in Fig. 2.b). Here we propose a new natural generalization of the Kautz graphs, obtained by extending the constraint on the sequences labeling the vertices, from adjacent positions to an arbitrary distance 𝑑. Definition 2. Given a sequence x = (π‘₯1 , . . . , π‘₯𝑛 ) ∈ Σ𝑛 we say that x is 𝑑-constrained, for some integer 𝑑, if for all 1 ≀ 𝑖, 𝑗 ≀ 𝑛, whenever π‘₯𝑖 = π‘₯𝑗 it holds |𝑖 βˆ’ 𝑗| β‰₯ 𝑑. Note that every sequence in Σ𝑛 is trivially 1-constrained while the sequences labeling Kautz graphs are 2-constrained. For any 𝑑-constrained x ∈ Σ𝑛 with |Ξ£| = 𝜎 it holds that 1 ≀ 𝑑 ≀ min{𝜎, 𝑛}. We denote by 𝑉 (𝜎, 𝑑, 𝑛) the set of all 𝑑-constrained sequences from the set Σ𝑛 . We now introduce 𝑑-constrained de Bruijn graphs. Definition 3. Given an alphabet Ξ£, with |Ξ£| = 𝜎, and two positive integers 𝑛 and 𝑑, with 1 ≀ 𝑑 ≀ min{𝜎, 𝑛}, we define the directed 𝑑-constrained de Bruijn graph of order 𝑛 on Ξ£ as the subgraph of the directed de Bruijn graph of order 𝑛 on Ξ£ induced by the set 𝑉 (𝜎, 𝑑, 𝑛). We denote a 𝑑-constrained directed de Bruijn graph with 𝑐𝐷𝐡(𝜎, 𝑑, 𝑛) and its undirected version with 𝑐𝐷𝐡 𝑒 (𝜎, 𝑑, 𝑛). Clearly, directed de Bruijn graphs and directed Kautz graphs coincide with 𝑐𝐷𝐡(𝜎, 1, 𝑛) and 𝑐𝐷𝐡(𝜎, 2, 𝑛), respectively. 11 13 13 21 12 21 32 21 32 13 22 31 32 23 12 23 12 23 33 31 31 a. b. c. Figure 1: For Ξ£ = {1, 2, 3} we show: (a) the directed de Bruijn graph 𝑐𝐷𝐡((, 𝜎, ,)1, 2); (b) the directed Kautz graph 𝑐𝐷𝐡(𝜎, 2, 2); (c) the undirected Kautz graph 𝑐𝐷𝐡 𝑒 (𝜎, 2, 2). In addition to their theoretical interest, 𝑑-constrained de Bruijn graphs may also find applica- tions in interconnection networks due to their sparsity and connectivity. Moreover, in some cases, these graphs could be more suitable than de Bruijn graphs in modelling problems. For example, in genome rearrangement, which is an important part of bioinformatics research, permutations of integers (i.e. 𝑛-constrained sequences) are used to represent genomes. Thus, 𝑛-constrained de Bruijn graphs could find applications in genome assembly [21, 22]. More generally, 𝑑-constrained sequences for 𝑑 < 𝑛 may be used to model genomes where duplication of genes is allowed only at a certain distance in the genome. In the full version of this extended abstract we provide a systematic study of the domination number of 𝑑-constrained de Bruijn graphs in both the directed and the undirected case. Although the domination numbers for de Bruijn and Kautz graphs have been exactly deter- mined (see [7] and [8, 23]), the exact values in the undirected cases are still missing. We are able to provide close upper and lower bounds on the value of 𝛾(𝑐𝐷𝐡 𝑒 (𝜎, 1, 𝑛)) and 𝛾(𝑐𝐷𝐡 𝑒 (𝜎, 2, 𝑛)). Furthermore, in the particular case when the sequences labeling the vertices are permutations (i.e. 𝑑 = 𝑛), we determine the exact value of the domination number in both the directed and undirected case. We also consider the case where the sequences are partial 𝑛-permutations on the set of symbols when |Ξ£| = 𝜎 = 𝑛 + 𝑐, for some integer 𝑐. In this case we are able to provide close upper and lower bounds for 𝛾(𝑐𝐷𝐡 𝑒 (𝑛 + 𝑐, 𝑛, 𝑛)) and 𝛾(𝑐𝐷𝐡(𝑛 + 𝑐, 𝑛, 𝑛)). Finally, we are able to provide upper and lower bounds for the domination number of 𝑐𝐷𝐡(𝜎, 𝑑, 𝑛). Concerning the value of 𝑐𝐷𝐡 𝑒 (𝜎, 𝑑, 𝑛) it remains an open problem to find an upper bound that is asymptotically better than the one trivially derived by the directed case. The results announced in this extended abstract are summarized in Table 1 and Table 2 for the directed and the undirected cases, respectively. All the proofs can be found in the full version of the paper [24]. We conclude this extended abstract with a comparison between the undirected and the directed cases. A dominating set for a directed graph is a fortiori also a dominating set for its underlying undirected graph. Thus, 𝛾(𝑐𝐷𝐡 𝑒 (𝜎, 1, 𝑛)) ≀ 𝛾(𝑐𝐷𝐡(𝜎, 1, 𝑛)). However, we improved this Graph 𝐺 𝛾(𝐺) ⌈︁ βŒ‰οΈ πœŽπ‘› 𝑐𝐷𝐡(𝜎, 1, 𝑛) 𝛾(𝐺) = 𝑑+1 [7] 𝑐𝐷𝐡(𝜎, 2, 𝑛) 𝛾(𝐺) = (𝜎 βˆ’ 1)π‘›βˆ’1 [8] π‘›βˆ’2 (︁ βˆ’ 2)(οΈ€ )οΈ€if)︁𝜎 even 𝛾(𝐺) = 𝜎(𝜎 𝑐𝐷𝐡(𝜎, 3, 𝑛) 𝜎(𝜎 βˆ’ 2) π‘›βˆ’2 ≀ 𝛾(𝐺) ≀ 1 + Θ 𝜎12 𝜎(𝜎 βˆ’ 2)π‘›βˆ’2 if 𝜎 odd π‘›βˆ’π‘‘ (︁ )οΈ€)︁ 𝜎! (πœŽβˆ’π‘‘+1)π‘›βˆ’π‘‘ 𝜎! (πœŽβˆ’π‘‘+1) 𝑑 (οΈ€ 𝑐𝐷𝐡(𝜎, 𝑑, 𝑛) (π‘‘βˆ’π‘‘)! (πœŽβˆ’π‘‘+2) ≀ 𝛾(𝐺) ≀ 1 + Θ 𝜎(πœŽβˆ’π‘‘+1) (πœŽβˆ’π‘‘)! (πœŽβˆ’π‘‘+2) 𝛾(𝐺) = 𝑛2 (𝑛 βˆ’ 1)! βŒˆοΈ€ βŒ‰οΈ€ 𝑐𝐷𝐡(𝑛, 𝑛, 𝑛) (︁ (οΈ€ 1 )οΈ€)︁ 1 (𝑛+𝑐)! 1 (𝑛+𝑐)! 𝑐𝐷𝐡(𝑛 + 𝑐, 𝑛, 𝑛) 𝑐+2 𝑐! ≀ 𝛾(𝐺) ≀ 1 + Θ 𝑐 𝑐+2 𝑐! Table 1 Summary of the results for 𝑑-constrained de Bruijn graphs. Results without a reference are proved in the full version of this extended abstract. Graph 𝐺 𝛾(𝐺) 𝑐𝐷𝐡 𝑒 (𝜎, 1, 2) 𝛾(𝐺) = 𝜎 βˆ’ 1 𝛾(𝐺) = 𝜎 𝑑2 βŒˆοΈ€ βŒ‰οΈ€ 𝑐𝐷𝐡 𝑒 (𝜎, 1, 3) (︁ (οΈ€ 1 )οΈ€)︁ πœŽπ‘› πœŽπ‘› 𝑐𝐷𝐡 𝑒 (𝜎, 1, 𝑛), 𝑛 β‰₯ 4 2𝜎+1 ≀ 𝛾(𝐺) ≀ 2 βˆ’ Θ 𝜎 2𝜎+1 𝑐𝐷𝐡 𝑒 (𝜎, 2, 2) 𝛾(𝐺) = 𝜎 βˆ’ 1 𝜎(πœŽβˆ’1) βŒŠοΈ€ 2 βŒ‹οΈ€ 𝑐𝐷𝐡 𝑒 (𝜎, 2, 3) 2 𝛾(𝐺) ≀ 𝜎2 (︁ (οΈ€ )οΈ€)︁ 𝜎(πœŽβˆ’1)π‘›βˆ’1 π‘›βˆ’1 𝑐𝐷𝐡 𝑒 (𝜎, 2, 𝑛), 𝑛 β‰₯ 4 2πœŽβˆ’1 ≀ 𝛾(𝐺) ≀ 2 βˆ’ Θ 𝜎1 𝜎(πœŽβˆ’1) 2πœŽβˆ’1 (︁ (οΈ€ 1 )οΈ€)︁ 𝜎(πœŽβˆ’1)(πœŽβˆ’2)π‘›βˆ’2 𝜎(πœŽβˆ’1)(πœŽβˆ’2)π‘›βˆ’2 𝑐𝐷𝐡 𝑒 (𝜎, 3, 𝑛) 2πœŽβˆ’3 ≀ 𝛾(𝐺) ≀ 2 βˆ’ Θ 𝜎 2πœŽβˆ’3 βŒˆοΈ€ 𝑛 βŒ‰οΈ€ 𝑐𝐷𝐡 𝑒 (𝑛, 𝑛, 𝑛) 𝛾(𝐺) = 3 (𝑛 βˆ’ 1)! (︁ )οΈ€)︁ 1 (𝑛+𝑐)! 1 (𝑛+𝑐)! ≀ 𝛾(𝐺) ≀ 1 + Θ 1𝑐 + 𝑛1 2𝑐+3 (οΈ€ 𝑐𝐷𝐡 𝑒 (𝑛 + 𝑐, 𝑛, 𝑛) 2𝑐+3 𝑐! 𝑐! Table 2 Summary of the results for undirected 𝑑-constrained de Bruijn graphs. Results without a reference are proved in the full version of this extended abstract. bound. Namely, for 𝑛 = 2 and 𝑛 = 3, we deduce 𝛾(𝑐𝐷𝐡 𝑒 (𝜎, 1, 2)) ≀ 𝜎 βˆ’ 1 + 𝜎+1 1 and 𝛾(𝑐𝐷𝐡 (𝜎, 1, 3)) ≀ 𝜎 βˆ’πœŽ+1, respectively, 𝑒 2 that are worse than our results 𝛾(𝑐𝐷𝐡 (𝜎, 1, 2)) = 𝑒 𝜎 βˆ’ 1 and 𝛾(𝑐𝐷𝐡 βŒ‰οΈ 1, 3)) = 𝜎 2 , respectively. For 𝑛 β‰₯ 4 the⌈︁(οΈ€upper bound provided for the 𝑒 βŒˆοΈ€ 𝜎 βŒ‰οΈ€ ⌈︁ (𝜎, )οΈ€ πœŽπ‘› βŒ‰οΈ πœŽπ‘› directed case is 𝑑+1 and the one from the undirected case is 1 βˆ’ 𝜎2 𝜎+1 . 1 Regarding 𝑑 = 2, the result proved in [8], gives us 𝛾(𝑐𝐷𝐡 𝑒 (𝜎, 2, 𝑛)) ≀ 𝛾(𝑐𝐷𝐡(𝜎, 2, 𝑛)) = (𝜎 βˆ’ 1)π‘›βˆ’1 . Our results show that, for 𝑛 = 2, 𝛾(𝑐𝐷𝐡 𝑒 (𝜎, 2, 𝑛)) = 𝛾(𝑐𝐷𝐡(𝜎, 2, 𝑛)) = 𝑑 βˆ’ 1. For 𝑛 β‰₯ 3 the upper bound of (𝜎 βˆ’ 1)π‘›βˆ’1 derived from the directed case is improved to (𝜎 βˆ’ 1)π‘›βˆ’1 βˆ’ (𝜎 βˆ’ 2)(𝜎 βˆ’ 1)π‘›βˆ’4 . Since 𝛾(𝑐𝐷𝐡 𝑒 (𝜎, 3, 𝑛)) ≀ 𝛾(𝑐𝐷𝐡(𝜎, 3, 𝑛)), for 𝜎 even we have an upper bound of 𝜎(𝜎 βˆ’ 2)π‘›βˆ’2 and in the undirected case we improve this result to (𝜎 βˆ’ 1)(𝜎 βˆ’ 2)π‘›βˆ’2 = 𝜎(𝜎 βˆ’ 2)π‘›βˆ’2 βˆ’ (𝜎 βˆ’ 2)π‘›βˆ’2 . For 𝜎 odd, we have (𝜎 βˆ’ 1)2 (𝜎 βˆ’ 2)π‘›βˆ’3 in the directed case and the improvement to (𝜎 βˆ’ 1)(𝜎 βˆ’ 2)π‘›βˆ’2 = (𝜎 βˆ’ 1)2 (𝜎 βˆ’ 2)π‘›βˆ’3 βˆ’ (𝜎 βˆ’ 1)(𝜎 βˆ’ 2)π‘›βˆ’3 in the undirected case. Finally, we have 𝛾(𝑐𝐷𝐡 𝑒 (𝑛 + 𝑐, 𝑛, 𝑛)) ≀ (𝑛+π‘βˆ’1)(𝑛+π‘βˆ’1)! (𝑐+1)! 𝑛+π‘βˆ’1 (𝑛+𝑐)! = (𝑛+𝑐)(𝑐+1) 𝑐! which is worse that the undirected result when 𝑛 goes to infinity. Furthermore, for small values of 𝑛 the results show that, while for 𝑛 = 2, 𝛾(𝑐𝐷𝐡 𝑒 (𝜎, 2, 𝑛)) = 𝛾(𝑐𝐷𝐡(𝜎, 2, 𝑛)) = 𝜎 βˆ’ 1, for 𝑛 β‰₯ 3 the upper bound of (𝜎 βˆ’ 1)π‘›βˆ’1 derived from the directed case can be already improved to (𝜎 βˆ’ 1)π‘›βˆ’1 βˆ’ (𝜎 βˆ’ 2)(𝜎 βˆ’ 1)π‘›βˆ’4 . References [1] S. T. Hedetniemi, R. C. Laskar, Bibliography on domination in graphs and some basic definitions of domination parameters, Discrete Mathematics 86 (1990) 257–277. [2] T. W. Haynes, S. T. Hedetniemi, P. J. Slater, Domination in Graphs, vol. 209 of Monographs and Textbooks in Pure and Applied Mathematics, Marcel Dekker, New York, USA., 1998. [3] F. Dai, J. Wu, An extended localized algorithm for connected dominating set formation in ad hoc wireless networks, IEEE Transactions on Parallel and Distributed Systems 15 (2004) 908–920. [4] T. MilenkoviΔ‡, V. MemiΕ‘eviΔ‡, A. Bonato, N. PrΕΎulj, Dominating biological networks, PLOS ONE 6 (2011) 1–12. [5] A. Bonato, M. Lozier, D. Mitsche, X. PΓ©rez-GimΓ©nez, P. PraΕ‚at, The domination number of on-line social networks and random geometric graphs, in: R. Jain, S. Jain, F. Stephan (Eds.), Theory and Applications of Models of Computation, Springer International Publishing, 2015, pp. 150–163. [6] M. R. Garey, D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co Ltd, 1979. [7] Z. Blazsik, Z. KΓ‘sa, Dominating sets in de Bruijn graphs, Pure mathematics and applications 13 (2002) 79–85. [8] Y. Kikuchi, Y. Shibata, On the domination numbers of generalized de Bruijn digraphs and generalized Kautz digraphs, Information Processing Letters 86 (2003) 400–408. [9] H. Yan, L. Kang, G. Xu, The exact domination number of the generalized Petersen graphs, Discrete Mathematics 309 (2009) 2596–2607. [10] M. Mollard, The domination number of cartesian product of two directed paths, Journal of Combinatorial Optimization 27 (2014) 144–151. [11] L. Badakhshian, G. O. Katona, Z. Tuza, The domination number of the graph defined by two levels of the n-cube, Discrete Applied Mathematics 266 (2019) 30–37. [12] J. Balogh, G. O. Katona, W. Linz, Z. Tuza, The domination number of the graph defined by two levels of the n-cube, II, European Journal of Combinatorics 91 (2021) 103201. [13] Y. Dong, E. Shan, L. Kang, Constructing the minimum dominating sets of generalized de Bruijn digraphs, Discrete Math. 338 (2015) 1501–1508. [14] Y. Orenstein, D. Pellow, G. MarΓ§ais, R. Shamir, C. Kingsford, Designing small universal k-mer hitting sets for improved analysis of high-throughput sequencing, PLOS Computa- tional Biology 13 (2017) 1–15. [15] P. A. Pevzner, H. Tang, M. S. Waterman, An eulerian path approach to DNA fragment assembly, Proceedings of the National Academy of Sciences 98 (2001) 9748–9753. [16] A.-H. Esfahanian, S. L. Hakimi, Fault-tolerant routing in De Bruijn communication networks, IEEE Trans. Comput. 34 (1985) 777–788. [17] M. F. Kaashoek, D. R. Karger, Koorde: A simple degree-optimal distributed hash table, in: M. F. Kaashoek, I. Stoica (Eds.), Peer-to-Peer Systems II, Springer Berlin Heidelberg, Berlin, Heidelberg, 2003, pp. 98–107. [18] D. Li, X. Lu, J. Su, Graph-Theoretic Analysis of Kautz Topology and DHT Schemes, in: H. Jin, G. R. Gao, Z. Xu, H. Chen (Eds.), Network and Parallel Computing, Springer Berlin Heidelberg, Berlin, Heidelberg, 2004, pp. 308–315. [19] W. H. Kautz, Bounds on directed (𝑑, π‘˜) graphs, Theory of cellular logic networks and machines 24 (1968) 20–28. [20] J.-C. Bermond, N. Homobono, C. Peyrat, Connectivity of kautz networks, Discrete Mathematics 114 (1993) 51–62. [21] M. A. Alekseyev, P. A. Pevzner, Colored de Bruijn graphs and the genome halving problem, IEEE/ACM Transactions on Computational Biology and Bioinformatics 4 (2007) 98–107. [22] Y. Lin, S. Nurk, P. A. Pevzner, What is the difference between the breakpoint graph and the de Bruijn graph?, BMC Genomics 15 (2014) S6. [23] T. Araki, On the π‘˜-tuple domination of de Bruijn and Kautz digraphs, Information Processing Letters 104 (2007) 86 – 90. [24] T. Calamoneri, A. Monti, B. Sinaimeri, On the domination number of 𝑑-constrained de bruijn graphs, 2021. URL: https://arxiv.org/abs/2112.10426.