On graphs having r different sizes of maximal independent sets and some extensions

Nesta tese, apresentamos alguns resultados relacionados, principalmente, aos tamanhos de conjuntos independentes maximais em alguns grafos. Mostramos que para inteiros r e D, com r 2 e D 3, há um número finito de grafos conexos de grau mínimo pelo menos 2, grau máximo até D e cintura pelo menos 7 que têm tamanhos de conjuntos independentes maximais de até r tamanhos diferentes. Além disso, provamos outros resultados que restringem os graus de tais grafos e que generalizam resultados já conhecidos sobre grafos bem-cobertos. Foram estudados a estrutura e o reconhecimento dos grafos bem-cobertos G de ordem n(G) sem vértice isolado que têm número de independência n(G)k 2 , para algum inteiro não negativo k. Para k = 1, apresentamos uma descrição estrutural completa destes grafos e para um k geral, porém fixo, descrevemos um algoritmo de complexidade polinomial de tempo para o reconhecimento de tais grafos. Consideramos grafos G sem vértice isolado cuja diferença entre o maior e o menor conjuntos independentes maximais é no máximo k, para algum inteiro k não negativo. Obtivemos um limite superior sobre o número de independência destes grafos. Apresentamos um algoritmo de complexidade polinomial de tempo para reconhecimento de alguns produtos complementares, o qual inclui todos os prismas complementares. Apresentamos também alguns resultados sobre prismas complementares bem-cobertos. Mostramos que se G não é um grafo bem-coberto e seu prisma complementar é bem-coberto, então G tem somente dois tamanhos de conjuntos independentes maximais que são consecutivos. Apresentamos um limite superior para a quantidade de tamanhos de conjuntos independentes maximais em prismas complementares e também outros resultados relacionados à bem-cobertura. Apresentamos um limite inferior para a quantidade de conjuntos independentes maximais de tamanhos diferentes em produtos Cartesianos de caminhos e ciclos. In this thesis, we present some results concerning about the sizes of maximal independent sets in graphs. We prove that for integers r and D with r 2 and D 3, there are only finitely many connected graphs of minimum degree at least 2, maximum degree at most D, and girth at least 7 that have maximal independent sets of at most r different sizes. Furthermore, we prove several results restricting the degrees of such graphs. These contributions generalize known results on well-covered graphs. We study the structure and recognition of the well-covered graphs G with order n(G) without an isolated vertex that have independence number n(G)k 2 for some non-negative integer k. For k = 1, we give a complete structural description of these graphs, and for a general but fixed k, we describe a polynomial time recognition algorithm. We consider graphs G without an isolated vertex for which the independence number a(G) and the independent domination number i(G) satisfy a(G) i(G) k for some non-negative integer k. We obtain a upper bound on the independence number in these graphs. We present a polynomial algorithm to recognize some complementary products, which includes all complementary prisms. Also, we present results on well-covered complementary prisms. We show that if G is not well-covered and its complementary prism is well-covered, then G has only two consecutive sizes of maximal independent sets. We present an upper bound for the quantity of sizes of maximal independent sets in complementary prisms and other wellcovered concerning results. We present a lower bound for the quantity of different sizes of maximal independent sets in Cartesian products of paths and cycles. Fundação de Amparo à Pesquisa do Estado de Goiás - FAPEG