On Some Results for the $L(2,1)$-Labeling on Cartesian Sum Graphs

Abstract

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)|\ge 2$ if $d(x,y)=1$ and $|f(x)–f(y)|\ge 1$ if $d(x,y)=2$, where $d(x,y)$ denotes the distance between vertices $x$ and $y$ in $G$. 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$. We consider Cartesian sums of graphs and derive, both, lower and upper bounds for the $L(2,1)$-labeling number of this class of graphs; we use two approaches to derive the upper bounds for the $L(2,1)$-labeling number and both approaches improve previously known upper bounds. We also present several approximation algorithms for computing $L(2,1)$-labelings for Cartesian sum graphs.