On L(h, k)-labelling of Caterpillars

• J. P. K. Castilho Unicamp http://orcid.org/0000-0003-4061-5790
• C. N. Campos Unicamp https://orcid.org/0000-0003-4237-4281
• L. M. Zatesko UTFPR

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

Abstract

An L(h, k)-labelling is an assignment σ of integers to the vertices of a simple graph such that the labels of: adjacent vertices are at least h apart; vertices having a common neighbour are at least k apart. The largest difference between the labels of any two vertices is the span of σ. Determining the L(h, k)-span, i.e. the least span amongst all σ, is NP-hard for trees. Caterpillars are a subclass of trees much studied in the context of labelling problems. We provide tight bounds for the L(h, k)-span of every caterpillar G, determining the exact value if k divides h and G has at most seven vertices in a maximum path.

Keywords: Graph Labelling, L(h, k)-labelling, Caterpillar graphs

References

Calamoneri, T. (2011). The L (h, k)-labelling problem: an updated survey and annotated bibliography. Comput. J., 54:1344–1371.

Calamoneri, T., Pelc, A., and Petreschi, R. (2006). Labeling trees with a condition at distance two. Discrete Math., 306(14):1534–1539.

Castilho, J. P. K., Campos, C. N., and Zatesko, L. M. (2021). Proper L (h, k)-labelling of caterpillars and multisunlets. Submitted.

Chang, G. J., Ke, W.-T., Kuo, D., Liu, D. D.-F., and Yeh, R. K. (2000). Discrete Math., 220:57–66.

Fiala, J., Golovach, P. A., and Kratochvı́l, J. (2008). Computational complexity of the distance constrained labeling problem for trees. In Proc. 35th International Colloquium on Automata, Languages, and Programming (ICALP ’08), pages 294–305.

Gallian, J. A. (2020). A dynamic survey of graph labeling. Eletron. J. Combin, (DS6).

Georges, J. and Mauro, D. (1995). Generalized vertex labelings with a condition at distance two. Congr. Numer., 109:141–159.

Griggs, J. R. and Jin, X. T. (2007). Real number labelings for paths and cycles. Internet Math., 4(1):65–86.

Griggs, J. R. and Yeh, R. K. (1992). Labelling graphs with a condition at distance 2. SIAM J. Discrete Math., 5:586–595.

Ladinek, I. H. and Žerovnik, J. (2020). On L (d, 1)-labelling of trees. Math. Interdisc. Res., 5(2):87–102.

Luiz, A. G., Campos, C. N., and Richter, R. B. (2020). Some families of 0-rotatable graceful caterpillars. Graphs Combin., 36:1655–1673.

Rosa, A. (1967). On certain valuations of the vertices of a graph. J. Graph Theory, pages 349–355.

Zhang, X. and Deng, K. (2016). The L (2, 1, 1)-labellings of caterpillars. Int. J. Comput. Math.: Comput. Syst. Theory, 1(3–4):85–97.