Parâmetros de dominância em grafos regulares

Abstract

Este trabalho é dedicado ao estudo de cotas superiores para parâmetros de dominância em grafos d-regulares. Nossos resultados foram obtidos por meio da aplicação de um método conhecido e versátil proposto por Wormald que envolve equações diferenciais e aleatoriedade em grafos. Estão envolvidas as áreas de Combinatória, Probabilidade e Análise. Um grafo G é dito d-regular se todo vértice tem grau d. Em um grafo G, um conjunto DT V (G) é dito totalmente dominante se todo vértice de G possui um vizinho em DT. Um conjunto Dk V (G) e dito k-dominante se todo vértice de G n Dk possui pelo menos k vizinhos em Dk. Os números de dominação total t(G) e de k-dominância k(G) são as menores cardinalidades possíveis de conjuntos DT e Dk com essas propriedades, respectivamente, para o grafo G fixado. Neste trabalho, analisamos algoritmos capazes de construir conjuntos totalmente dominantes e 2-dominantes em grafos aleatórios d-regulares. Essas análises estabeleceram cotas superiores, válidas assintoticamente quase certamente, para os números t(G)=jV (G)j e 2(G)=jV (G)j em função de d. As cotas probabilísticas produzidas aqui são melhores do que as cotas determinísticas encontradas na literatura para todos os valores de d >/ para os quais a cota foi efetivamente calculada. Adicionalmente, a aplicação de um resultado recente de Hoppen e Wormald permite que essas mesmas cotas sejam válidas como cotas determinísticas para todos os grafos d-regulares G com cintura g(G) suficientemente grande, onde a cintura g(G) de um grafo G e o comprimento do menor ciclo contido em G.

This work is dedicated to the study of upper bounds on domination parameters in d-regular graphs. Our results were obtained through the application of a well-known and versatile method proposed by Wormald that involves diferential equations and randomness in graphs. The areas of Combinatorics, Probability and Analysis are involved. A graph G is said to be d-regular if every vertex has degree d. In a graph G, a set DT V (G) is said to be totally dominating if every vertex of G has a neighbor in DT . A set Dk V (G) is k-dominating if every vertex of G n Dk has at least k neighbors in Dk. The total domination number t(G) and the k- domination number k(G) are the smallest possible cardinalities of sets DT and Dk with these properties, respectively, for a xed graph G. In this work, we analyze the performance, in random regular graphs, of algorithms capable of constructing totally dominating sets and 2-dominating sets in d-regular graphs. This analysis leads to upper bounds, valid asymptotically almost surely, on t(G)=jV (G)j and 2(G)=jV (G)j as a function of d. The probabilistic bounds produced here are better than the deterministic bounds found in the literature for all values d 3 for which they have been computed. In addition to this, the application of a recent result of Hoppen and Wormald implies that essentially the same bounds are valid as deterministic bounds for all d-regular graphs G with girth g(G) su ciently large, where the girth g(G) of a graph G is the length of the shortest cycle in G.