On (s,t)-relaxed L(1,1)-labelling of trees

ABSTRACT

Suppose G is a graph. Let u be a vertex of G. A vertex v is called an i-neighbour of u if $d_G(u,v)=i$. A 1-neighbour of u is simply called a neighbour of u. Let s and t be two non-negative integers. Suppose f is an assignment of non-negative integers to the vertices of G. If, for any vertex u of G, the number of neighbours v (resp. 2-neighbours w) of u with $f\left(v\right)=f\left(u\right)$ (resp. $f\left(w\right)=f\left(u\right)$) is at most s (resp. t), then f is called an $(s,t)$-relaxed $L(1,1)$-labelling of G. The span of f, denoted by $\mathrm{span}\left(f\right)$, is the difference between the maximum and minimum integers used by f. The minimum span of $(s,t)$-relaxed $L(1,1)$-labellings of G is called the $(s,t)$-relaxed $L(1,1)$-labelling number of G, denoted by ${\lambda }_{1,1}^{s,t}\left(G\right)$. It is clear that ${\lambda }_{1,1}^{0,0}\left(G\right)$ is the so called $L(1,1)$-labelling number of G. This paper studies the $(s,t)$-relaxed $L(1,1)$-labellings of trees. Let T be a tree with maximum degree Δ. It is proved that $\lceil (\mathrm{\Delta }-s)/(t+1)\rceil \le {\lambda }_{1,1}^{s,t}\left(T\right)\le \lceil (\mathrm{\Delta }-s+t)/(t+1)\rceil$ and both lower and upper bounds are attainable. For s=0 and $t\ge 1$ fixed, a polynomial-time algorithm is designed to determine if ${\lambda }_{1,1}^{s,t}\left(T\right)$ equals the lower bound.

KEYWORDS:

• $L(j,k)$-labelling
• $(s,t)$-relaxed $L(1,1)$-labelling
• tree
• complete Δ-regular tree
• channel assignment

2010 AMS SUBJECT CLASSIFICATION:

• 05C15

Disclosure statement

No potential conflict of interest was reported by the authors.

Additional information

Funding

Supported by Natural Science Foundation of Jiangsu Province of China [No. BK20151399].