Número (p,1)-total de near-ladders e Petersen generalizados
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.
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.
Publicado
31/07/2022
Como Citar
OMAI, M. M.; CAMPOS, C. N.; LUIZ, A. G..
Número (p,1)-total de near-ladders e Petersen generalizados. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 7. , 2022, Niterói.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2022
.
p. 105-108.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2022.223153.
