\(L(2,1)\)-Labeling of Cartesian Product of Complete Bipartite Graph and Path

An \(L(2,1)\)-labeling problem is a particular case of \(L(h,k)\)-labeling problem. An \(L(2,1)\)-labeling of a graph \(G=(V,E)\) is a function \(f\) from the set of vertices \(V\) to the set of positive integers. For any two vertices \(x\) and \(y\), the label difference \(|f(x)-f(y)|\geq2\) when \(d(x,y)=1\) and \(|f(x)-f(y)|\geq1\) when \(d(x,y)=2\) where \(d(x,y)\) is the distance between the vertices \(x\) and \(y\). In this paper we label the graph which is obtained by Cartesian product between complete bipartite graph and path by \(L(2,1)\)-labeling. We provide upper bound of the label in terms of number of vertices and edges. The bound is linear with respect to the order and size of the graph. This is a very good bound compare to the bound of Griggs and Yeh Conjecture.