On the (2,1)-total number of indifference graphs

• M. M. Omai CEFET/RJ / Unicamp https://orcid.org/0000-0002-7858-6481
• C. N. Campos Unicamp https://orcid.org/0000-0003-4237-4281
• Atílio G. Luiz UFC https://orcid.org/0000-0002-6177-403X

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

Resumo

A k-(2, 1)-total labelling of a graph G is a function π : V (G) ∪ E(G) → {0, . . . , k} such that: π(u) ̸= π(v) for every uv ∈ E(G); π(uv) ̸= π(vw) for every pair of adjacent edges uv, vw ∈ E(G); and |π(uv)−π(u)| ≥ 2 and |π(uv) − π(v)| ≥ 2 for every uv ∈ E(G). The least integer k for which G admits a k-(2, 1)-total labelling is denoted by λ^t₂(G). In this work, we establish tight upper bounds for λ^t₂(G) when G is an indifference graph, according to the parity of ∆(G). We also determine the (2, 1)-total number of powers of paths P^l_n with n = 2l vertices, a subclass of indifference graphs.

Referências

Chia, M.-L., Kuo, D., Yan, J.-H., and Yang, S.-R. (2013). (p,q)-total labeling of complete graphs. Journal of Combinatorial Optimization, 25(4):543–561.

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.

Hale, W. K. (1980). Frequency assignment: Theory and applications. Proceedings of the IEEE, 68(12):1497–1514.

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

Omai, M. M., Campos, C. N., and Luiz, A. G. (2022). The (2,1)-total number of powers of paths and powers of cycles. In Annals of the Latin-American Workshop on Cliques in Graphs (LAWCG 2022).