COTAS DO TIPO NORDHAUS-GADDUM PARA O NÚMERO DE ANIQUILAÇÃO
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-Gaddum
⌊n/2⌋ ≤ a(G) ≤ n 2⌊n/2⌋ ≤ a(G) + a(Gc) ≤ n + 2⌊n/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.
COTAS DO TIPO NORDHAUS-GADDUM PARA O NÚMERO DE ANIQUILAÇÃO
-
DOI: 10.22533/at.ed.0772128041
-
Palavras-chave: Número de Aniquilação; Problema de Nordhaus-Gaddum; Propriedade do Intervalo; Problemas Extremais.
-
Keywords: Annihilation number; Nordhaus-Gaddum problem; Interval property; Extremal problems.
-
Abstract:
Let G be a graph with n vertices and Gc be its complement. The Annihilation number of G, denoted by a(G), is the largest integer k such that the sum of k smallest degrees of G is at most the number of edges. This invariant is a sharp upper bound for the independence number. In this work, we present the following bounds and Nordhaus-Gaddum type inequalities for the Annihilation number
⌊n/2⌋ ≤ a(G) ≤ n 2⌊n/2⌋ ≤ a(G) + a(Gc) ≤ n + 2⌊n/2⌋
We also investigate the extremal behavior of the invariant and showed that both parameters satisfy the interval property. In addition, we characterize some extremal graphs, ensuring that the bounds obtained are the best possible.
-
Número de páginas: 10
- Daniel Alejandro Jaume
- Marco Puliti Lartigue
- Guilherme Porto
