The \(L(2,1)\)-labeling on planar graphs (Q868019)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The \(L(2,1)\)-labeling on planar graphs |
scientific article |
Statements
The \(L(2,1)\)-labeling on planar graphs (English)
0 references
19 February 2007
0 references
For a simple graph \(G\), \(\lambda (G)\) is the smallest non-negative integer \(m\) such that there is a function \(f\) from \(V(G)\) to the set of non-negative integers which has the property that \(| f(u)-f(v)| \geq 2\) if \(d(u,v)=1\) and \(| f(u)-f(v)| \geq 1\) if \(d(u,v)=2\). Using standard inequalities derived from Euler's theorem and a few other well-known results, the authors derive a series of upper bounds on \(\lambda\) which improve on known results for planar graphs of appropriately low maximum degree. In 1992, Griggs and Yeh conjectured that for \(G\) with maximum degree \(\Delta\), \(\lambda \leq \Delta^{2}\); see \textit{J. R. Griggs} and \textit{R. K. Yeh} [SIAM J. Discrete Math. 5, 586--595 (1992; Zbl 0767.05080)]. In the present paper an infinite sequence of graphs satisfying the conjecture is presented.
0 references
channel assignment
0 references
distance two graph labeling
0 references