×

Labeling cacti with a condition at distance two. (English) Zbl 1223.05265

Summary: An \(L(2,1)\)-labeling of a graph \(G\) is a function \(f\) from the vertex set \(V(G)\) to the set of all nonnegative integers such that \(|f(x)- f(y)|\geq 2\) if \(d(x, y)= 1\) and \(|f(x)- f(y)|\geq 1\) if \(d(x, y)= 2\). The \(L(2,1)\)-labeling number \(\lambda(G)\) of \(G\) is the smallest number \(k\) such that \(G\) has an \(L(2,1)\)-labeling with \(\max\{f(v): v\in V(G)\}\) = k. In [SIAM J. Discrete Math. 5, No. 4, 586–595 (1992; Zbl 0767.05080)], it has been proved by J. R. Griggs and R. K. Yeh that the \(2k\)-number of a tree is \(\Delta+ 1\) or \(\Delta+ 2\). In this paper we present a graph family other than the trees whose \(\lambda\)-number is \(\Delta+1\) or \(\Delta+ 2\).

MSC:

05C78 Graph labelling (graceful graphs, bandwidth, etc.)

Citations:

Zbl 0767.05080
PDFBibTeX XMLCite
Full Text: Link