On efficient absorbant conjecture in generalized De Bruijn digraphs
Autor: | Yue-Li Wang, Kuo-Hua Wu, Ton Kloks |
---|---|
Rok vydání: | 2016 |
Předmět: |
De Bruijn sequence
Discrete mathematics Mathematics::Combinatorics Conjecture Applied Mathematics Digraph 0102 computer and information sciences 02 engineering and technology 01 natural sciences 020202 computer hardware & architecture Computer Science Applications Combinatorics De bruijn digraph Computational Theory and Mathematics Computer Science::Discrete Mathematics 010201 computation theory & mathematics Dominating set 0202 electrical engineering electronic engineering information engineering Computer Science::Data Structures and Algorithms Mathematics |
Zdroj: | International Journal of Computer Mathematics. 94:922-932 |
ISSN: | 1029-0265 0020-7160 |
DOI: | 10.1080/00207160.2016.1154949 |
Popis: | An absorbant of a digraph D is a set such that, for every , there exists an arc with . An absorbant S is efficient if no two vertices in S have a common in-neighbour and the subdigraph induced by S has no arc. The efficient absorbant conjecture in generalized De Bruijn digraphs is as follows: There exists an efficient absorbant in generalized De Bruijn digraph with if and only if c is a multiple of . In this paper, we show that the sufficient condition of the efficient absorbant conjecture in generalized De Bruijn digraphs is affirmative. |
Databáze: | OpenAIRE |
Externí odkaz: |