Geodesic
The maximum independent sets of de Bruijn graphs of diameter 3
The electronic journal of combinatorics, Tome 18 (2011) no. 1
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

The nodes of the de Bruijn graph $B(d,3)$ consist of all strings of length $3$, taken from an alphabet of size $d$, with edges between words which are distinct substrings of a word of length $4$. We give an inductive characterization of the maximum independent sets of the de Bruijn graphs $B(d,3)$ and for the de Bruijn graph of diameter three with loops removed, for arbitrary alphabet size. We derive a recurrence relation and an exponential generating function for their number. This recurrence allows us to construct exponentially many comma-free codes of length 3 with maximal cardinality.
DOI : 10.37236/681
Classification : 05C69, 05A15, 05C12 
@article{10_37236_681,
     author = {Dustin A. Cartwright and Mar{\'\i}a Ang\'elica Cueto and Enrique A. Tobis},
     title = {The maximum independent sets of de {Bruijn} graphs of diameter 3},
     journal = {The electronic journal of combinatorics},
     year = {2011},
     volume = {18},
     number = {1},
     doi = {10.37236/681},
     zbl = {1229.05217},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/681/}
}
TY  - JOUR
AU  - Dustin A. Cartwright
AU  - María Angélica Cueto
AU  - Enrique A. Tobis
TI  - The maximum independent sets of de Bruijn graphs of diameter 3
JO  - The electronic journal of combinatorics
PY  - 2011
VL  - 18
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.37236/681/
DO  - 10.37236/681
ID  - 10_37236_681
ER  - 
%0 Journal Article
%A Dustin A. Cartwright
%A María Angélica Cueto
%A Enrique A. Tobis
%T The maximum independent sets of de Bruijn graphs of diameter 3
%J The electronic journal of combinatorics
%D 2011
%V 18
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/681/
%R 10.37236/681
%F 10_37236_681
Dustin A. Cartwright; María Angélica Cueto; Enrique A. Tobis. The maximum independent sets of de Bruijn graphs of diameter 3. The electronic journal of combinatorics, Tome 18 (2011) no. 1. doi: 10.37236/681

Cité par Sources :