On L(d, 1)-labelling of trees

Hrastnik Ladinek, Irena (author), Žerovnik, Janez (author)

Given a graph ▫$G$▫ and a positive integer ▫$d$▫, an ▫$L(d,1)$▫-labelling of ▫$G$▫ is a function ▫$f$▫ that assigns to each vertex of ▫$G$▫ a non-negative integer such that if two vertices ▫$u$▫ and ▫$v$▫ are adjacent, then ▫$|f(u)-f(v) |\ge d$▫ and if ▫$u$▫ and ▫$v$▫ are at distance two, then ▫$|f(u)-f(v)| \ge 1$▫. The ▫$L(d,1)$▫-number of ▫$G$▫, ▫$\lambda_d(G)$▫, is the minimum ▫$m$▫ such that there is an ▫$L(d,1)$▫-labelling of ▫$G$▫ with ▫$f(V) \subseteq \{0,1,\dots , m\}$▫. A tree ▫$T$▫ is of type 1 if ▫$\lambda_d(T) = \Delta+d-1$▫ and is of type 2 if ▫$\lambda_d(T) \ge \Delta+d$▫. This paper provides sufficient conditions for ▫$\lambda_d(T)=\Delta+d-1$▫ generalizing the results of Wang [W. Wang, The ▫$L(2,1)$▫-labeling of trees, Discrete Appl. Math. 154 (2006) 598-603] and Zhai, Lu, and Shu [M. Zhai, C. Lu and J. Shu, A note on ▫$L(2,1)$▫-labeling of Trees, Acta. Math. Appl. Sin. 28 (2012) 395-400] for ▫$L(2,1)$▫-labelling.

• Language: English
• Keywords: L(d, 1)-labelling, tree, distance, [Delta]-vertex
• Work type: Article
• Typology: 1.01 - Original Scientific Article
• Organization: FS - Faculty of Mechanical Engineering
• Publication status: Published
• Publication version: Version of Record
• Year: 2020
• Number of pages: Str. 87-102
• Numbering: Vol. 5, iss. 2
• PID: 20.500.12556/RUL-134485
• UDC: 519.17
• ISSN on article: 2476-4965
• DOI: 10.22052/mir.2020.227370.1211
• COBISS.SI-ID: 20362243
• Publication date in RUL: 18.01.2022

Record is a part of a journal

• Title: Mathematics interdisciplinary research
• Shortened title: Math. interdiscip. res.
• Publisher: University of Kashan
• ISSN: 2476-4965
• COBISS.SI-ID: 18230361

Licences

• License: CC BY 4.0, Creative Commons Attribution 4.0 International
• Link: http://creativecommons.org/licenses/by/4.0/
• Description: This is the standard Creative Commons license that gives others maximum freedom to do what they want with the work as long as they credit the author.
• Licensing start date: 18.06.2020

Secondary language

• Language: Slovenian
• Keywords: matematika, teorija grafov, drevo