Let b;l be a pair of positive integers, in this work we discuss the problem of finding an independent set L with [L] =l nodes in the hypercube graph Qb such that the open neighborhood NQb(L) has minimum cardinality jNQb(L)j = Opt(b; l). The interest in this problem was arouse through the study of Hamming-Huffman trees, which aim the integration between data compaction and errors detection, in the data transmission context. The process of building this type of tree is still an open problem that seems to be directly related to the minimum neighborhood of independent sets in Qb. Searching for an eficient solution for this problem, we defined a special graph denoted by Q2b, whose cliques have had many of their properties determined and turned out to be the basis for two polynomial time algorithms in b and l. These algorithms finds an independent set L of Qb such that jNQb(L)j = v(b; l) Opt(b; l) that we have conjectured to be a solution for this problem
Neste trabalho abordamos o problema onde, dado um par de inteiros positivos l e b, deseja-se encontrar um conjunto independente L com [L] = l nós no grafo b-cubo Qb, tal que L possua uma vizinhança com cardinalidade mínima Opt(b; l). O interesse neste problema surgiu através do estudo inicial de árvores Hamming-Huffman, que visam a integração entre compactação de dados e detecção de erros, no contexto de transmissão de dados. A criação desta árvore um problema em aberto que parece estar diretamente relacionado com vizinhanças em Qb. Na busca de uma solução eficiente para o problema de mínimos um grafo especial, Q2b, cujas cliques tiveram diversas propriedades determinadas e que foram base para dois algoritmos polinomiais em ` e b. Esses algoritmos determinam um conjunto independente L 2 V (Qb), [L] = l, de V (Qb) com vizinhança N(L) de tamanho [N(L)] = v(b; l) maior que Opt(b; l) que conjecturamos ser uma solução para esse problema
