Desigualdades do Tipo Nordhaus-Gaddum para o Número de Aniquilação

PORTO, GUILHERME; JAUME, DANIEL ALEJANDRO; PULITI, MARCO

Revista Mundi Engenharia, Tecnologia e Gestão (ISSN: 2525-4782)

Instituto Federal Paraná

Año: 2021 vol. 6

Seja G um grafo com n vértices e Gc seu complemento. O número de aniquilação de G, denotado por a(G), é o maior número inteiro k tal que a soma dos k menores graus de G não ultrapassa seu número de arestas. Esse invariante é usado como cota superior para o número de independência do grafo. Neste trabalho, apresentamos as seguintes cotas para o número de aniquilação e seu problema de Nordhaus GaddumTambém investigamos o comportamento extremal desses invariantes e mostramos que satisfazem a propriedade do intervalo. Além disso, caracterizamos alguns grafos extremais, garantindo que as cotas obtidas são as melhores possíveis.