×

Labeling chordal graphs: Distance two condition. (English) Zbl 0794.05118

An \(L_ d(2,1)\)-labeling \(f\) of a graph \(G= (V,E)\) is a map \(f: V\to \mathbb{R}^ +\cup \{0\}\) with the property that, if \(x\) and \(y\) are two adjacent vertices, then \(| f(x)- f(y)|\geq 2d\), and, if the distance between \(x\) and \(y\) is two, then \(| f(x)- f(y)|\geq d\), \(d\in \mathbb{R}^ +\). Putting \(d=1\) the author investigates the so-called \(L(2,1)\)-labeling number \(\lambda(G)\) of \(G\) and determines upper bounds of \(\lambda(G)\), \(G\) is an arbitrary chordal graph, depending on the maximum degree \(\Delta(G)\). In the second part, the author considers unit interval graphs \(G\) and then succeeds in finding a better upper bound of \(\lambda(G)\) depending on the chromatic number \(\chi(G)\). The author concludes his paper by formulating some open problems on upper bounds of the \(L(2,1)\)-labeling number \(\lambda(G)\).
Reviewer: R.Bodendiek (Kiel)

MSC:

05C78 Graph labelling (graceful graphs, bandwidth, etc.)
05C12 Distance in graphs
Full Text: DOI