On Radio Connection Number of Graphs

Abstract

Given a graph G and a vertex coloring c, G is called l-radio connected if between any two distinct vertices u and v there is a path such that coloring c restricted to that path is an l-radio coloring. The smallest number of colors needed to make G l-radio connected is called the l-radio connection number of G. In this paper we introduce these notions and initiate the study of connectivity through radio colored paths, providing results on the 2-radio connection number, also called L(2, 1)-connection number: lower and upper bounds, existence problems, exact values for known classes of graphs and graph operations.

Keywords

• radio connection number
• radio coloring
• l(2, 1)-connection number
• l(2, 1)-connectivity
• l(2, 1)-labeling
• 05c15
• 05c40
• 05c38