Article ID Journal Published Year Pages File Type
4649225 Discrete Mathematics 2006 16 Pages PDF
Abstract

In this paper, we give several exact values of the independence number of a de Bruijn graph UB(d,D)UB(d,D) and in the other cases, we establish pertinent lower and upper bounds of this parameter. We show that asymptotically, if d   is even, the ratio of the number of vertices of a greatest independent set of UB(d,D)UB(d,D) is 12.

Keywords
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Preview
Independence number of de Bruijn graphs
Authors
,