On circular-L(2, 1)-labellings of products of graphs

Abstract

Let m, j and k be positive integers. An m-circular-L(j, k)-labelling of a graph G is an assignment f from { 0, 1, … , m−1} to the vertices of G such that, for any two vertices u and v, |f(u)−f(v)|_m≥j if uv∈E(G), and |f(u)−f(v)|_m≥k if d_G(u, v)=2, where |a|_m=min{a, m−a}. The minimum m such that G has an m-circular-L(j, k)-labelling is called the circular-L(j, k)-labelling number of G. This paper determines the circular-L(2, 1)-labelling numbers of the direct product of a path and a complete graph and of the Cartesian product of a path and a cycle.

Keywords:

• L(2, 1)-labelling number
• circular-L(2, 1)-labelling number
• direct product
• Cartesian product
• path
• cycle
• complete graph

2010 AMS Subject Classification:

• 05C15

ACM Computing Classification System Code:

• G.2.2

Acknowledgements

We would like to give our thanks to the referees for their valuable comments and remarks. Project 10971025 supported by NSFC.