Número (p,1)-total de near-ladders e Petersen generalizados

• M. M. Omai UNICAMP
• C. N. Campos UNICAMP
• A. G. Luiz UFC

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

Resumo

Uma k-rotulação (p, 1)-total de um grafo simples G é uma função π: V(G) ∪ E(G) → {0, . . . , k} em que: |π(uv)−π(u)| ≥ p e |π(uv)−π(v)| ≥ p para uv ∈ E(G); π(uv) ≠ π(vw) para uv, vw ∈ E(G); e π(u) ≠ π(v) para uv ∈ E(G). O menor inteiro k para o qual G admite uma k-rotulação (p, 1)-total é denotado por λ_p^t(G). Neste trabalho, provamos que: λ_p^t(G) = p + 4, p ≥ 3, para os grafos near-ladder não bipartidos e para os grafos de Petersen generalizados P(ℓ, 2), ℓ ≥ 6; e λ_2^t(G) = 5 para P(ℓ, 2), ℓ ≥ 6

Palavras-chave: Rotulação (2,1)-total, número (2,1)-total, rotulação (p,1)-total, número (p,1)-total, Petersen generalizados, near-ladders

Referências

Chunling, T., Xiaohui, L., Yuansheng, Y., e Zhengwei, H. (2010). (d, 1)-total labellings of regular nonbipartite graphs and an application to flower snarks. Ars Comb., 96:33–40.

Deng, X., Shao, Z., Zhang, H., e Yang, W. (2019). The (d, 1)-total labelling of sierpinskilike graphs. Appl. Math. Comput., 361:484–492.

Havet, F., Reed, B., e Sereni, J.-S. (2008). L(2, 1)-labelling of graphs. In Proc. Annu. ACM-SIAM Symp., pages 621–630. Society for Industrial and Applied Mathematics.

Havet, F. e Thomassé, S. (2009). Complexity of (p, 1)-total labelling. Discrete Appl. Math., 157(13):2859–2870.

Havet, F. e Yu, M.-L. (2008). (p,1)-total labelling of graphs. Discrete Math., 308(4):496 – 513.

Krnc, M. e Pisanski, T. (2019). Characterization of generalised petersen graphs that are kronecker covers. Acta Math. Univ. Comen., 88(3):891–895.

Montassier, M. e Raspaud, A. (2006). (d, 1)-total labeling of graphs with a given maximum average degree. J. Graph Theory, 51(2):93–109.

Omai, M. M., Campos, C. N., e Luiz, A. G. (2021). The (2, 1)-total number of near-ladder graphs. In Anais do VI ETC.

Sethuraman, G. e Velankanni, A. (2015). (2, 1)-total labeling of a class of subcubic graphs. Electron. Notes Discrete Math., 48:259–266.

Sun, L. e Wu, J.-L. (2017). On (p, 1)-total labelling of planar graphs. J. Comb. Optim., 33(1):317–325.