On L(h,k)-labelings of oriented graphs

• Lucas Colucci USP https://orcid.org/0000-0002-7390-8314

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

Resumo

We compare the behaviour of the $L(h,k)$-number of undirected and oriented graphs in terms of maximum degree, highlighting differences between the two contexts. In particular, we prove that, for every $h$ and $k$, oriented graphs with bounded degree in every block of their underlying graph (for instance, oriented trees and oriented cacti) have bounded $L(h,k)$-number, giving an upper bound on this number which is sharp up to a multiplicative factor $4$.

Palavras-chave: graph labeling, L(2,1)-labeling, graph theory

Referências

Chang, G. J., Chen, J.-J., Kuo, D., and Liaw, S.-C. (2007). Distance-two labelings of digraphs. Discrete applied mathematics, 155(8):1007–1013.

Chang, G. J. and Liaw, S.-C. (2003). The L(2, 1)-labeling problem on ditrees. Ars Combinatoria, 66:23–31.

Chen, Y.-T., Chia, M.-L., and Kuo, D. (2009). L(p, q)-labeling of digraphs. Discrete applied mathematics, 157(8):1750–1759.

Colucci, L. and Gyori, E. (2021+). On L(2, 1)-labelings of oriented graphs. Discussiones Mathematicae Graph Theory. In press.

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

Yeh, K.-C. (1990). Labeling graphs with a condition at distance two. PhD thesis, University of South Carolina.