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 2023): 0.5

5-year Journal Impact Factor (2023): 0.6

CiteScore (2024): 2.1

SNIP (2024): 1.162

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(2,1)$-labeling, directed graphs

References:

  1. K.-C. Yeh, Labeling Graphs with a Condition at Distance Two, Ph.D. Thesis (University of South Carolina, 1990).
  2. G.J. Chang and S.-C. Liaw, The ${L}(2, 1)$-labeling problem on ditrees, Ars Combin. 66 (2003) 23–31.
  3. J.R. Griggs and R.K. Yeh, Labelling graphs with a condition at distance $2$, SIAM J. Discrete Math. 5 (1992) 586–595.
    https://doi.org/10.1137/0405048
  4. T. Calamoneri and B. Sinaimeri, $L(2, 1)$-labeling of oriented planar graphs, Discrete Appl. Math. 161 (2013) 1719–1725.
    https://doi.org/10.1016/j.dam.2012.07.009
  5. W.K. Hale, Frequency assignment: Theory and applications, Proc. IEEE 68 (1980) 1497–1514.
    https://doi.org/10.1109/PROC.1980.11899
  6. T. Calamoneri, The ${L}(h,k)$-labelling problem: an updated survey and annotated bibliography, available on (2014).
    http://www.dsi.uniroma1.it/$\sim$calamo/PDF-FILES/survey.pdf
  7. R.K. Yeh, A survey on labeling graphs with a condition at distance two, Discrete Math. 306 (2006) 1217–1231.
    https://doi.org/10.1016/j.disc.2005.11.029
  8. F. Havet, B. Reed and J.-S. Sereni, $L(2, 1)$-labelling of graphs, in: Proc. Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms (2008) 621–630.
  9. C. Lu and Q. Zhou, Path covering number and ${L}(2, 1)$-labeling number of graphs, Discrete Appl. Math. 161 (2013) 2062–2074.
    https://doi.org/10.1016/j.dam.2013.02.020
  10. T. Calamoneri, The $L(h, k)$-labelling problem: an updated survey and annotated bibliography, Comput. J. 54 (2011) 1344–1371.
    https://doi.org/10.1093/comjnl/bxr037
  11. G. Chartrand, F. Harary and P. Zhang, On the geodetic number of a graph, Networks 39 (2002) 1–6.
    https://doi.org/10.1002/net.10007
Close