On the (p,1)-total number of near-ladders and generalized Petersen graphs

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

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

Abstract

A k-(p, 1)-total labelling of a simple graph G is a function π: V(G)∪E(G) → {0, . . . , k} such that: |π(uv) − π(u)| ≥ p and |π(uv) − π(v)| ≥ p for uv ∈ E(G); π(uv) ≠ π(vw) for uv, vw ∈ E(G); and π(u) ≠ π(v) for uv ∈ E(G). The least integer k for which G admits a k-(p, 1)-total labelling is denoted λ_p^t(G). In this work, we show that: λ_p^t(G) = p + 4, p ≥ 3, for non-bipartite near-ladder graphs and generalized Petersen graphs P(ℓ, 2), ℓ ≥ 6; and λ_2^t(G) = 5 for graphs P(ℓ, 2), ℓ ≥ 6.

Keywords: (2,1)-total labelling, (2,1)-total number, (p,1)-total labelling, (p,1)-total number, generalized Petersen graphs, near-ladder graphs

References

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.