108
Views
5
CrossRef citations to date
0
Altmetric
Section A

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

, &
Pages 475-482 | Received 12 Jun 2012, Accepted 08 Oct 2012, Published online: 14 Feb 2013
 

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 3×C n of the triangle and a cycle C n for all the other n. In fact, we show that among these n, λ(K 3×C n )=7 for all n≠7, 11 and λ(K 3×C n )=8 when n=7, 11.

2000 AMS Subject Classifications:

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.

Reprints and Corporate Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

To request a reprint or corporate permissions for this article, please click on the relevant link below:

Academic Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

Obtain permissions instantly via Rightslink by clicking on the button below:

If you are unable to obtain permissions via Rightslink, please complete and submit this Permissions form. For more information, please visit our Permissions help page.