Limites superiores para a rotulação L(3,2,1) de famílias de grafos subcúbicos - Florencio, Davi Gomes; Luiz, Atílio Gomes (Anais do Encontro de Teoria da Computação (ETC); 2021: Anais do VI Encontro de Teoria da Computação, 2021)
Uma rotulação L(3,2,1) de um grafo G é uma função f de V(G) em S = {0,1,...,k} tal que |f(u)-f(v)| >= 4 - d(u,v) para quaisquer dois vértices u, v em V(G), em que d(u,v) é a distância entre u e v em G. O span de uma rotulação L(3,2,1) f é o maior rótulo k em S. O menor span que uma rotulação L(3,2,1) pode atribuir a um grafo G é denotado por lambda_{3,2,1}(G). Neste trabalho, provamos que lambda_{3,2,1}(G) = 25 para todo grafo subcúbico G sem vértices adjacentes de grau máximo. Além disso, provamos que lambda_{3,2,1}(G) <= 16 para grafos subcúbicos G com vértices de grau 3 à distância pelo menos 4.