On the Sizes of Maximal Independent Sets of Cylindrical Grid Graphs

RESUMO. Se um grafo G tem exatamente t tamanhos diferentes de conjuntos independentes maximais, G pertence a uma coleção chamada ℳ t . Para o produto Cartesiano do grafo Pn , o caminho de tamanho n, e Cm , o ciclo de tamanho m, chamado grade cilíndrica, apresentamos um método para encontrar conjuntos independentes maximais com diferentes tamanhos e um limite inferior para t, tal que estes grafos pertençam à ℳ t .

• Assuntos:

  • Grafo bem-coberto
  • conjunto independente maximal
  • produto Cartesiano