L(h, k)-labelling for octagonal grid

Abstract

An $L(h,k)$-labelling of a graph G is an assignment of nonnegative integers, called labels, to the vertices of G such that two adjacent vertices receive labels that differ by at least h and those of distance two receive labels that differ by at least k. Among the span of all $L(h,k)$-labellings of G, ${\lambda }_{h,k}(G)$ is the smallest one. In this paper for the octagonal grid $G_8$, we show that the upper bound for ${\lambda }_{h,k}(G_8)$ is $3h+6k$ when $h\ge 4k$. And when $h>6k$, we show that ${\lambda }_{h,k}(G_8)=3h+6k$.

Keywords:

• L(h, k)-labelling
• octagonal grid
• channel assignment problem
• wireless network
• strong product

2010 AMS Subject Classifications:

• 05C15
• 05C78
• 05C38

Acknowledgments

We are thankful to the referees whose valuable comments led to the improvement in all over the presentation of the paper. This work was supported by the Research Institute of Natural Science of Gangneung-Wonju National University.