Número Cromático Antimágico Local de Algumas Subclasses de Árvores Rosas Perfeitas

Resumo

Seja G = (V, E) um grafo simples, conexo, de ordem n e tamanho m. Para a terminologia fundamental da teoria dos grafos, seguimos [2]. O número cromático de um grafo G é o menor número de rótulos distintos que podem ser atribuídos aos seus vértices, de modo que vértices adjacentes recebam rótulos diferentes. Em contextos mais recentes, surgiram variantes que consideram rotulações de arestas, como a rotulação antimágica local. O estudo dessas rotulações fornece informações estruturais adicionais sobre o grafo e apresenta aplicações em áreas como alocação de frequência e criptografia. Seja f : E → {1, 2, . . . , m} uma bijeção sobre as arestas de G. Para cada v ∈ V, o peso de v é dado por f⁺(v) = Σ_e∈E(v) f(e), onde E(v) denota o conjunto das arestas que incidem em v. Quando f⁺(v) ≠ f⁺(u) para cada par de vértices u, v adjacentes em G, a bijeção f é denominada rotulação antimágica local de G. Assim, qualquer rotulação antimágica local induz uma rotulação dos vértices de G, definida pelos pesos f⁺(v) atribuídos a cada vértice v. Um grafo G é dito antimágico local se G possui uma rotulação antimágica local. O número cromático antimágico local de G, denotado por χ_la(G), é o menor número de pesos distintos atribuídos aos vértices, considerando todas as possíveis rotulações antimágicas locais de G. Considere o caminho P₆, com vértices V = {v₁, v₂, v₃, v₄, v₅, v₆} e arestas E = {e₁, e₂, e₃, e₄, e₅}. Na Figura 1, apresentamos a rotulação antimágica local de P₆, conforme [1], a qual determina seu número cromático antimágico local. Foi provado em [1] que, para toda árvore T com ℓ folhas, o número cromático antimágico local satisfaz a desigualdade χ_la(T) ≥ ℓ + 1. Além disso, os autores em [3] conjecturaram que χ_la(T) ≤ ℓ + 2 e propuseram uma caracterização das árvores em que χ_la(T) = ℓ + 1. Motivados por estes problemas, investigamos o número cromático antimágico local das árvores rosas perfeitas, que definimos a seguir. Dados inteiros positivos k e r, a árvore rosa perfeita R_k,r é obtida ao conectar o vértice central de um caminho de ordem ímpar P_2k+1 ao vértice central de uma estrela S_r de ordem r. A seguir, enunciamos alguns dos resultados originais que obtivemos durante nossas pesquisas e que respondem aos problemas enunciados acima para algumas subclasses das árvores rosas perfeitas. [...]