On Radio Connection Number of Graphs

摘要

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.