DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

Journal Impact Factor (JIF 2022): 0.7

5-year Journal Impact Factor (2022): 0.7

CiteScore (2022): 1.9

SNIP (2022): 0.902

Discussiones Mathematicae Graph Theory

Article in volume

Authors:

L. Colucci

Lucas Colucci

Alfréd Rényi Institute of Mathematics, Hungarian Academy of Sciences, Reáltanoda u. 13–15, 1053 Budapest, Hungary
Central European University, Department of Mathematics and its Applications, Nádor u. 9, 1051 Budapest, Hungary

email: lucascolucci@renyi.hu

E. Győri

Ervin Győri

Alfréd Rényi Institute of Mathematics, Hungarian Academy of Sciences, Reáltanoda u. 13–15, 1053 Budapest, Hungary
Central European University, Department of Mathematics and its Applications, Nádor u. 9, 1051 Budapest, Hungary

email: gyori.ervin@renyi.mta.hu

Title:

On $L(2,1)$-labelings of oriented graphs

PDF

Source:

Discussiones Mathematicae Graph Theory 42(1) (2022) 39-46

Received: 2019-02-14 , Revised: 2019-06-21 , Accepted: 2019-06-21 , Available online: 2019-09-30 , https://doi.org/10.7151/dmgt.2240

Abstract:

We extend a result of Griggs and Yeh about the maximum possible value of the $L(2,1)$-labeling number of a graph in terms of its maximum degree to oriented graphs. We consider the problem both in the usual definition of the oriented $L(2,1)$-labeling number and in some variants we introduce.

Keywords:

$L(21)$-labeling, directed graphs

References:

  1. Yeh, Kwan-Ching, Labeling graphs with a condition at distance two, Phd thesis, University of South Carolina (1990).
  2. Chang, Gerard J and Liaw, Sheng-Chyang, The {L}(2, 1)-labeling problem on ditrees, Ars Combinatoria 66 (2003) 23–31.
  3. Griggs, Jerrold R and Yeh, Roger K, Labelling graphs with a condition at distance 2, SIAM Journal on Discrete Mathematics 5(4) (1992) 586–595.
  4. Calamoneri, Tiziana and Sinaimeri, Blerina, L(2, 1)-labeling of oriented planar graphs, Discrete Applied Mathematics 161(12) (2013) 1719–1725.
  5. Hale, William K, Frequency assignment: Theory and applications, Proceedings of the IEEE 68(12) (1980) 1497–1514.
  6. Calamoneri, Tiziana, The {L}(h,k)-labelling problem: an updated survey and annotated bibliography, available on \url{http://www.dsi.uniroma1.it/$\sim$calamo/PDF-FILES/survey.pdf} (2014).
  7. Yeh, Roger K, A survey on labeling graphs with a condition at distance two, Discrete Mathematics 306(12) (2006) 1217–1231.
  8. Havet, Frédéric and Reed, Bruce and Sereni, Jean-Sébastien, L(2, 1)-labelling of graphs, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete Algorithms (2008) 621–630, Society for Industrial and Applied Mathematics.
  9. Lu, Changhong and Zhou, Qing, Path covering number and {L}(2, 1)-labeling number of graphs, Discrete Applied Mathematics 161(13-14) (2013) 2062–2074.
  10. Calamoneri, Tiziana, The {L}(h, k)-labelling problem: an updated survey and annotated bibliography, The Computer Journal 54(8) (2011) 1344-1371.
  11. G. Chartrand, F. Harary and P. Zhang, On the geodetic number of a graph, Networks 39 (2002) 1–6.
Close