Conjuntos dominantes em grafos cúbicos Hamiltonianos

Resumo:

Em 1996, B. Reed provou que todo grafo conexo com grau mínimo pelo menos 3 possui número de dominação (dominating number) menor ou igual a 3n/8, onde n é o número de vértices do grafo. Neste mesmo trabalho, B. Reed conjecturou que o "teto" de n/3 seria um limitante superior para o número de dominação dos grafos cúbicos. Posteriormente, Plummer conjecturou que para grafos cúbicos hamiltonianos o "piso" de n/3 seria um limitante superior para o número de dominação. Neste seminário, será apresentado o traballho de Cropper, Greenwell, Hilton e Kostochka que demonstra que a conjectura de Plummer é verdadeira quando n é congruente a 0(mod 3) e a 1(mod 3) e falsa quando é congruente a 2(mod 3).