Mathematics and Computer Science: Research Updates Vol. 11

Graph labelling is an assignment of nonnegative integers, sometimes called colours, to the vertices, edges or both. Radio labelling is a well-known concept in graph theory, motivated by practical problems such as frequency assignment in communication networks.

Let (V, Ε) be a simple, connected and undirected graph. A radio labeling of G, ψ: V → {1,2,3,… } is a function satisfying the condition for any two distinct vertices u and v that: d(u,v) + |ψ(u) - ψ(v)| ≥ 1 + diam(G) where d(u,v) denotes the distance between the vertices u and v and diam(G) denotes the diameter of the graph G. The span of a radio labelling is the maximum integer that assigns to a vertex, and radio number, rn(G), is the minimum span taken overall radio labellings of G. This paper presents some bounds connecting radio number with clique number and the chromatic number. In addition, the possible constructions of simple connected graphs with radio number as the algebraic sum of the clique number and a non-negative integer. Also, a graph with radio number equal to the algebraic sum of chromatic number and a non-negative integer.