On \(L(d,1)\)-labelings of graphs (Q1567607): Difference between revisions
From MaRDI portal
Changed an Item |
Set OpenAlex properties. |
||
(One intermediate revision by one other user not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/s0012-365x(99)00400-8 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2058787498 / rank | |||
Normal rank |
Latest revision as of 10:16, 30 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On \(L(d,1)\)-labelings of graphs |
scientific article |
Statements
On \(L(d,1)\)-labelings of graphs (English)
0 references
29 January 2001
0 references
For a graph \(G\) and positive integer \(d\) an \(L(d,1)\)-labeling of \(G\) is defined as a function \(f: V_G\to {\mathbb{Z}}^{i\geq 0}\) such that \(|f(u)-f(v)|\geq d\) if \(uv\in E_G\) and \(|f(u)-f(v)|\geq 1\) if \(uv\not\in E_G\) and \(u,v\) are connected by a path. The \(L(d,1)\)-number of \(G\), \(\lambda_d(G)\), is a minimal number \(m\) such that there exists an \(L(d,1)\)-labeling \(f\) of \(G\) with the image \(\{1,2,\dots,m\}\). The authors extend the study of the number \(\lambda_d(G)\) from the extensively studied case \(d=2\) to arbitrary \(d\geq 2\). The main result is an upper bound \(\lambda_d(G)\leq \Delta^2 + (d-1)\Delta\) for any graph with maximum degree \(\Delta\). More specific results (lower and upper bounds) are obtained for chordal graphs and their various subclasses, in particular trees. It is shown that the bounds for trees are attainable.
0 references
graph labeling
0 references
vertex-coloring
0 references