The (2,1)-total number of near-ladder graphs

• M. M. Omai Unicamp
• C. N. Campos Unicamp https://orcid.org/0000-0003-4237-4281
• A. G. Luiz UFC https://orcid.org/0000-0002-6177-403X

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

Resumo

A $(2,1)$-total labelling of a simple graph $G$ is a function $\pi \colon V(G)\cup E(G) \to \{0, \ldots, k\}$ such that: $\pi(u) \neq \pi(v)$ for $uv \in E(G)$; $\pi(uv) \neq \pi(vw)$ for $uv, vw \in E(G)$; and $|\pi(uv)-\pi(u)| \geq 2$ and $|\pi(uv)-\pi(v)| \geq 2$ for $uv \in E(G)$. The $(2,1)$-total number $\lambda_2^t(G)$ of $G$ is the least $k$ for which $G$ admits such a labelling. In 2008, Havet and Yu conjectured that $\lambda_2^t(G)\leq 5$ for every connected graph $G \not\cong K_4$ with $\Delta(G) \leq 3$. We prove that, for near-ladder graphs, $\lambda_2^t(G)=5$, verifying Havet and Yu's Conjecture for this class.

Palavras-chave: Graph labelling, (2,1)-total labelling, cubic graphs, near-ladder

Referências

Chang, G. J. and Kuo, D. (1996). The L(2, 1)-labeling problem on graphs. SIAM Journalon Discrete Mathematics, 9(2):309–316.

Fiala, J., Kloks, T., and Kratochvíl, J. (2001). Fixed-parameter complexity of λ-labelings. Discrete Applied Mathematics, 113(1):59–72.

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 Thomassé, S. (2009). Complexity of (p, 1)-total labelling. Discrete Applied Mathematics, 157(13):2859–2870.

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

Khan, N., Pal, M., and Pal, A. (2010). (2, 1)-total labeling of cactus graphs.Journal ofInformation and Computing Science, 5:243–260.

Lih, K.-W., Liu, D. D.-F., and Wang, W. (2009). On (d, 1)-total numbers of graphs. Discrete Mathematics, 309(12):3767–3773.

Metzger, B. (1970). Spectrum management technique presented at 38th national orsameeting. Detroit, MI (Fall 1970).

Sethuraman, G. and Velankanni, A. (2015). (2, 1)-total labeling of a class of subcubicgraphs. Electronic Notes Discrete Mathematics, 48:259–266.

Tong, C., Xiaohui, L., Yuansheng, Y., and Zhengwei, H. (2010). (d, 1)-total labellingsof regular nonbipartite graphs and an application to flower snarks. Ars Combinatoria,96:33–40.

Wang, W. and Chen, D. (2009). (2, 1)-total number of trees with maximum degree three. Information Processing Letters, 109(14):805–810.

Zoeliner, J. A. and Beall, C. L. (1977). A breakthrough in spectrum conserving frequencyassignment technology. IEEE Transactions on Electromagnetic Compatibility, (3):313–319.