30 out 2020
10:00 Defesa de Mestrado Integralmente a distância
Tema
Conjuntos Dominantes em Grafos Cúbicos
Aluno
Alessandra Aparecida Pereira
Orientador / Docente
Christiane Neme Campos
Breve resumo
Um conjunto S ⊆ V (G) é um conjunto dominante se todo vértice de G é um elemento de S ou é adjacente a um elemento de S. Um conjunto dominante independente de G é, ao mesmo tempo, um conjunto dominante e um conjunto independente em G. Denominamos a cardinalidade de um menor conjunto dominante de G como número de dominação. Este parâmetro é denotado por γ(G). Neste trabalho, apresentamos um breve histórico sobre os problemas de conjuntos dominantes e algumas de suas variações. Destas variações, em particular, abordamos o número de dominação independente de G, denotado por i(G) e definido como a cardinalidade de um menor conjunto dominante independente de G. Determinar γ(G) e i(G) para um grafo arbitrário G são problemas NP-difı́ceis, mesmo quando restritos a grafos cúbicos. De fato, há muito interesse no estudo dos grafos cúbicos no contexto de dominação. Em particular, em 1996, B. Reed conjecturou que grafos cúbicos conexos G possuem γ(G) ≤ ⌈n/3⌉. Embora A. Kostochka e B. Stodolsky tenham mostrado que esta conjectura é falsa no caso geral, muita pesquisa tem sido feita em busca de famílias de grafos cúbicos que verificam ou melhoram o limitante de Reed. Neste texto, determinamos o número de dominação e o número de dominação independente de algumas famílias de grafos cúbicos. Além disso, outro ponto abordado neste texto é a relação entre γ(G) e i(G). Como todo conjunto dominante independente é um conjunto dominante, segue que γ(G) ≤ i(G). Decidir se γ(G) = i(G) também é um problema NP-completo. De fato, mesmo quando restrita a grafos cúbicos e conexos, a diferença i(G) − γ(G) pode ser arbitrariamente grande. Todas estas considerações motivam tanto o estudo dos grafos cúbicos com número de dominação limitado pelo valor da conjectura de Reed, como também a determinação do número de dominação independente destes grafos, para avaliar o quão distantes estes dois parâmetros estão. Neste trabalho, esta análise é feita para as classes consideradas.
Banca examinadora
Titulares:
| Christiane Neme Campos | IC/UNICAMP |
| José Coelho de Pina Junior | IME/USP |
| Orlando Lee | IC/UNICAMP |
Suplentes:
| Guilherme Pimentel Telles | IC/UNICAMP |
| Carmen Cecilia Centeno | ECEC/PUC Goiás |