Conjuntos independentes de vizinhança mínima no b-cubo

Abstract

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