Radio number of ladder graphs

Abstract

Let G be a connected graph with diameter diam(G). The radio number for G, denoted by rn(G), is the smallest integer k such that there exists a function f: V(G)→{0, 1, 2, …, k} with the following satisfied for all vertices u and v:|f(u)−f(v)|≥diam (G)−d _G (u, v)+1, where d _G (u, v) is the distance between u and v in G. In this paper, we determine the radio number of ladder graphs.

Keywords:

• channel assignment problem
• distance-two labelling
• multi-level distance labelling
• radio number
• radio labelling

2010 AMS Subject Classifications :

• 05C78
• 05C38
• 05C12

Acknowledgements

The authors are grateful to the referees for their valuable comments and suggestions.

The research is supported by the National Natural Science Foundation of China (60973014, 11001035), Specialized Research Fund for the Doctoral Program of Higher Education (200801411073) and Research Foundation of DLUT.