Holes in L(3, 2, 1)-Labeling

Abstract

An $ L(3, 2, 1) $-labeling is a simplified model for the channel assignment problem. Given a graph G, an $ L(3, 2, 1) $-labeling of G is a function $f$ from the vertex set $V(G)$ to the set of all non-negative integers such that $|f(u)- f(v)|\geq 1$ if $ d(u,v)=3 $, $|f(u)- f(v)|\geq 2$ if $ d(u,v)= 2 $ and $|f(u)- f(v)|\geq 3 $ if $ d(u,v)=1. $ The span of a labeling $f$, is the difference between the largest label and the smallest label in an $ L(3 ,2, 1) $-labeling. The $ L(3, 2, 1) $-labeling number of G, denoted by $\lambda_{3, 2, 1} (G)$, is the minimum span of all $ L(3, 2, 1) $-labelings of G. A span labeling is an $ L(3, 2, 1) $-labeling whose largest label is $\lambda_{3, 2, 1}(G)$. Let $f$ be an $ L(3, 2, 1) $-labeling that uses labels from 0 to $\lambda_{3, 2, 1}(G).$ Then $h \in (0, \lambda_{3, 2, 1}(G) )$ is a hole if there is no vertex $ v\in V (G)$ such that $f (v) = h$. In this paper, we investigate maximum number of holes in $ L(3, 2, 1) $ span labeling of certain classes of graphs.