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.
NP-hard [
Here we focus on the well-known de Bruijn graphs which have various applications in
diferent areas as for example bioinformatics [
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. 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 applications 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
determined (see [
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, ) (, 2, ) (, 3, ) (, , ) (, , ) ( + , , ) the full version of this extended abstract.
Summary of the results for undirected -constrained de Bruijn graphs. Results without a reference are proved in the full version of this extended abstract. ( − For ≥ 3 the upper bound of ( − ⌈︁ ⌉︁
+1 − 1 and ((, 1, 3)) = ⌈︀ 2 ⌉︀ , respectively. For ≥ bound. Namely, for = 2 and = 3, we deduce ((, 1, 2)) ≤ − ((, 1, 3)) ≤ 2− +1, respectively, that are worse than our results ((, 1 1 + +1 and
1, 2)) = 4 the upper bound provided for the directed case is and the one from the undirected case is (︀ 1 ⌈︁ − 2 1 )︀ ⌉︁ +1 .
Regarding = 2, the result proved in [
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)! = (+ +)(− +11) (+!)! 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. k-mer hitting sets for improved analysis of high-throughput sequencing, PLOS Computational 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 diference 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.