Limites superiores para a rotulação L(3,2,1) de famílias de grafos subcúbicos

• Davi Gomes Florencio UFC
• Atílio Gomes Luiz UFC https://orcid.org/0000-0002-6177-403X

DOI: https://doi.org/10.5753/etc.2021.16392

Resumo

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.

Palavras-chave: teoria dos grafos, rotulação em grafos, coloração em grafos, grafos subcúbicos

Referências

Brooks, R. L. (1941). On colouring the nodes of a network.Math. Proc. CambridgePhilos. Soc., 37:194–197.

Chartrand, G., Erwin, D., Harary, F., and Zhang, P. (2001). Radio labelings of graphs.Bulletin of the Institute of Combinatorics and its Applications, 33:77–85.

Chia, M. L., Kuo, D., Yang, H. L. C. H., and Yeh, R. K. (2011). L(3,2,1) labeling ofgraphs.Taiwanese Journal of Mathematics, 15:2439–2457.

Clipperton, J., Gehrtz, J., Szaniszlo, Z., and Torkornoo, D. (2006). L(3,2,1)-labeling ofsimples graphs.VERUM, 68:1497–1514.

Griggs, J. R. and Yeh, R. K. (1992). Labelling graphs with a condition at distance 2.SIAM Journal on Discrete Mathematics, 5(4):586–595.

Kral, D. and Skrekovski, R. (2003). A theorem about the channel assignment problem.SIAM Journal on Discrete Mathematics, 16:426–437.

Liu, J. and Shao, Z. (2004). The L(3,2,1)-labeling problem on graphs.MathematicaApplicata, 17(4):596–602.

West, D. B. (2018).Introduction to Graph Theory. Pearson Modern Classic.