| A. Ciências Exatas e da Terra - 2. Ciência da Computação - 17. Ciência da Computação |
|
ALGUMAS PROPRIEDADES PARA GRAFOS Zm-BEM-COBERTOS E P-REGULARES-ESTÁVEIS
|
|
| Aliny Figueirêdo Meira 1 |
| Rommel Melgaço Barbosa 1 |
|
| (1. Universidade Federal de Goiás (UFG)/ Instituto de Informática (INF)) |
|
|
| INTRODUÇÃO: |
O reconhecimento de grafos Zm-bem-cobertos é um problema co NP-completo em geral, porém é polinomial para algumas classes de grafos, tais como grafos cúbicos , livres de K1,3, simpliciais, cordais e com cintura >5 .Os grafos bem-cobertos foram introduzidos por Plummer em 1970 . Esta classe de grafos é importante porque o problema de determinar o número de independência de um grafo arbitrário é NP-Completo, mas para os grafos bem-cobertos o problema é polinomial, é necessário determinar o tamanho de um único conjunto independente maximal.Os grafos bem-cobertos de cintura ³ 8 foram caracterizados por Finbow e Hartnell ; este resultado foi extendido para os grafos bem-cobertos de cintura 5 ou mais por Finbow, Hartnell e Nowakowski . No entanto quando a restrição de ciclo é definida para conter somente ciclos de tamanho igual a 4 o problema se torna mais difícil. Os grafos bem-cobertos livres de K1,3 que não contém ciclos de tamanho igual a 4 foram caracterizados por Whitehead.O propósito do projeto é estudar caracterizações para os grafos Zm-bem-cobertos e bem-cobertos para algumas classes de grafos, e a partir deste estudo encontrar propriedades adicionais para os grafos Zm-bem-cobertos e bem-cobertos de cintura < 6 e cintura < 5, respectivamente. |
|
| METODOLOGIA: |
– Levantamento Bibliográfico.
Foram realizados estudos, pesquisas e leituras de artigos, papers e outros materiais de referência relativos à caracterização dos grafos Zm-bem-cobertos e bem-cobertos para algumas classes de grafos.
– Leitura Detalhada do Material Bibliográfico e Formulação de Conjecturas.
Uma leitura mais detalhada do material bibliográfico era realizada, na qual propunha-se encontrar exemplos que satisfaziam as definições e os Teoremas, encontrar contra-exemplos para mostrar que determinadas condições não eram válidas. Esta análise incluía também a criação de perguntas, conjecturas com base na observação de características comuns, de padrões que se repetiam através dos exemplos.
– Formalização dos Resultados. As demonstrações das principais caracterizações eram analisadas sucintamente, de forma a familiarizar o aluno com a formalização de provas de Teoremas. Com isso, inicia-se o processo de validação das conjecturas levantadas na fase anterior, seguida da prova formal dos resultados. |
|
| RESULTADOS: |
Provamos uma propriedade para vértices extensíveis de grafos Zm-bem-cobertos de cintura ³ 6. Através do estudo da caracterização dos grafos bem-cobertos de cintura ³ 5 encontramos uma outra família de grafos Zm-bem-cobertos de cintura £ 5..
Foi obtida uma Conjectura que representa uma forma de reescrever o Teorema 4 (Caro, Hartnell), que realça a relação entre os grafos Zm-bem-cobertos e os grafos simpliciais. Uma outra Conjectura formulada é uma adaptação do Teorema 4 (Caro, Hartnell) que ilustra uma família de grafos Zm-bem-cobertos de cintura igual a 4.
|
|
| CONCLUSÕES: |
Até o momento, a caracterização dos grafos bem-cobertos e Zm-bem-cobertos conforme a cintura se restringia a grafos com cintura ³ 5 e cintura ³ 6, respectivamente. No entanto, caracterizar os grafos bem-cobertos de cintura < 5 e grafos Zm-bem-cobertos de cintura < 6 se mostrou um problema difícil. Este trabalho conseguiu encontrar famílias de grafos com estas propriedades.
Mas ainda existem outros problemas a serem considerados, como por exemplo obter uma caracterização dos grafos bipartidos Zm-bem-cobertos, para a qual, já existe uma caracterização de grafos bem-cobertos.
|
|
Instituição de fomento: CNPQ
|
|
Trabalho de Iniciação Científica
|
|
Palavras-chave: Conjuntos independentes maximais; grafos Zm-bem-cobertos; grafos bem-cobertos. |
|
| Anais da 58ª Reunião Anual da SBPC - Florianópolis, SC - Julho/2006 |
|