Primeira defesa de tese do Programa de Pós-graduação em Ciência da Computação

O Programa de Pós-graduação em Ciência da Computação (Convênio UFG/UFMS), do Instituto de Informática da UFG convida para a defesa da primeira tese de doutorado do Programa, que será defendida pela doutoranda Márcia Rodrigues Cappelle Santana, no dia 01 de outubro, às 9h, na sala 151 do INF, com o título: "Sobre grafos com r tamanhos diferentes de conjuntos independentes maximais e algumas extensões", sob orientação do professor Rommel Melgaço Barbosa. A banca será composta pela professora da COPPE/UFRJ, Nair Maria Maia de Abreu, pelo professor do IME/UNICAMP, José Plínio de Oliveira Santos e pelo professor do INF/UFG, Humberto José Longo

Resumo da Tese: "Nesta tese, apresentamos alguns resultados relativos, 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 dois, grau máximo até D e cintura pelo menos sete que tem 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 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 reconhecimento de tempo polinomial. 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 polinomial 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. Para o produto Cartesiano do grafo Pn , o caminho de tamanho n, n ≥ 2 e Cm , o ciclo de tamanho m, m ≥ 3, denotado por Pn Cm e chamado de grade cilíndrica, apresentamos um limite inferior para a quantidade de tamanhos de conjuntos independentes maximais."