L(2, 1)-labellings for direct products of a triangle and a cycle

Abstract

An L(2, 1)-labelling of a graph G is a vertex labelling such that the difference of the labels of any two adjacent vertices is at least 2 and that of any two vertices of distance 2 is at least 1. The minimum span of all L(2, 1)-labellings of G is the λ-number of G and denoted by λ(G). Lin and Lam computed λ(G) for a direct product G=K _m ×P _n of a complete graph K _m and a path P _n . This is a natural lower bound of λ(K _m ×C _n ) for a cycle C _n . They also proved that when n≡ 0±od 5m, this bound is the exact value of λ(K _m ×C _n ) and computed the value when n=3, 5, 6. In this article, we compute the λ-number of G, where G is the direct product K ₃×C _n of the triangle and a cycle C _n for all the other n. In fact, we show that among these n, λ(K ₃×C _n )=7 for all n≠7, 11 and λ(K ₃×C _n )=8 when n=7, 11.

Keywords:

• L(2, 1)-labelling
• direct product
• triangle
• cycle

2000 AMS Subject Classifications:

• 05C78
• 05C38

Acknowledgements

We are grateful to referees for their valuable suggestions and comments on the earlier draft of the article. This work is supported by the University of Incheon research grant in 2009–2010.