Sobre Rotulações L(h, k) de 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

Resumo

Uma rotulação L(h, k) é uma atribuição σ de inteiros aos vértices de um grafo simples tal que os rótulos de: vértices adjacentes diferem de pelo menos h; vértices com um vizinho em comum diferem de pelo menos k. A maior diferença entre os rótulos de quaisquer dois vértices é o span de σ. Determinar o L(h, k)-span, i.e. o menor span para todas as rotulações σ, é NP-difı́cil para árvores. Caterpillars são uma subclasse das árvores muito estudada no contexto de problemas rotulação. Nós provamos limitantes justos para o L(h, k)-span de todo caterpillar G, determinando o valor exato se k divide h e G tem no máximo sete vértices em um caminho máximo.

Palavras-chave: Rotulação de Grafos, Rotulação L(h, k), Grafos caterpillars

Referências

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.