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

Guilherme Porto, Daniel Alejandro Jaume, Marco Puliti

Resumo


Seja G um grafo com n vértices e 𝐺𝑐 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-Gaddum: ⌊𝑛/2⌋ ≤ 𝑎(𝐺) ≤ 𝑛  e  2⌊𝑛/2⌋ ≤ 𝑎(𝐺) + 𝑎(𝐺𝑐) ≤ 𝑛 + ⌊𝑛/2⌋.També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.

Palavras-chave


Número de Aniquilação. Problema de Nordhaus-Gaddum. Propriedade do Intervalo. Problemas Extremais.

Texto completo:

PDF


DOI: http://dx.doi.org/10.21575/25254782rmetg2021vol6n31662

Apontamentos

  • Não há apontamentos.


Direitos autorais 2021 Guilherme Porto, Daniel Alejandro Jaume, Marco Puliti

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

Qualis: B4 - Interdisciplinar, B5 - Geografia, B5 - Administração Pública e de Empresas, Ciências Contábeis e Turismo, B5 - Comunicação e Informação, B5 - Engenharias III