Efficient absorbants in generalized de Bruijn digraphs
| Autor: | Tzong-Huei Shiau, Yue-Li Wang, Alexander Chane Shiau |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
De Bruijn sequence
Discrete mathematics Vertex (graph theory) Conjecture Applied Mathematics 020206 networking & telecommunications Digraph 0102 computer and information sciences 02 engineering and technology 01 natural sciences Theoretical Computer Science Combinatorics De bruijn digraph Computational Theory and Mathematics 010201 computation theory & mathematics Dominating set 0202 electrical engineering electronic engineering information engineering Greatest common divisor Mathematics |
| Zdroj: | Discrete Optimization. 25:77-85 |
| ISSN: | 1572-5286 0020-7160 |
| DOI: | 10.1016/j.disopt.2017.01.005 |
| Popis: | Let D = ( V , A ) be a digraph with vertex set V and arc set A . An efficient absorbant (respectively, dominating set) of a digraph D = ( V , A ) is a set S ⊆ V such that, for every v ∈ V ∖ S , there exists exactly one out-neighbor (respectively, in-neighbor) of v in S and there is no arc in the induced digraph of S , where an out-neighbor (respectively, in-neighbor) of v in S is a vertex u with an arc ( v , u ) (respectively, ( u , v ) ) in A with u ∈ S . The efficient absorbant conjecture is as follows: there is an efficient absorbant in generalized de Bruijn digraph G B ( n , d ) if and only if n d + 1 is a multiple of gcd ( n , d − 1 ) , where gcd ( x , y ) denotes the greatest common divisor of integers x and y . The sufficient condition of this conjecture was proved in DOI: 10.1080/00207160.2016.1154949 . In this paper, we settle the conjecture. Moreover, we also show that, the subclasses in G B ( n , d ) having efficient absorbants and efficient dominating sets are equivalent. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect