The Channel Assignment problem(CAP) is a general framework focused on point-to-point communication, e.g. in radio or mobile telephone networks. One of its main threads asks for an assignment of frequencies or frequency channels to transmitters while keeping interference at an acceptable level and making use of the available channels in an efficient way. Thus the main task of the channels assignment problem is to assign channels to the station in a way that avoids interference and uses spectrum as efficient as possible. Radio k-colorings of graphs is a variation of channels assignment problem. For a simple connected graph G with diameter q, and an integer k, 1 6 k 6 q, a radio k-coloring of G is an assignment f of non-negative integers to the vertices of G such that |f (u) − f (v)| > k + 1 − d(u, v) for each pair of distinct vertices u and v of G, where d(u, v) is the distance between u and v in G. The span of a radio k-coloring f , rck (f ), is the maximum integer assigned by it to some vertex of G. The radio k-chromatic number, rck (G) of G is min{rck (f )}, where the minimum is taken over all possible radio k-colorings f of G. For k = q and k = q − 1 the radio k-chromatic number of G is termed as the radio number (rn(G)) and antipodal number (ac(G)) of G respectively. Radio k-chromatic number is known for very limited families of graphs and specific values of k (e.g. k = q, q − 1, q − 2).For this research talk only we discuss the results which are related to the radio number of graphs. For an n-vertex graph G, we shall discuss about a lower bound of rn(G) which depends on a parameter based on a Hamiltonian path in a metric closure Gc (an n-vertex complete weighted graph where weight of an edge uv is dG (u, v)). Using this result we show that how we can derive lower bounds of rn(Cn ), rn(Pm Pn ), rn(Cm Cn ), rn(Cm Pn ) and rn(Km Cn ). For any tree T an improved lower bound of radio number depending on maximum weight Hamiltonian path of T have been shown. Next we discuss about an upper bound of rn(G) by giving a coloring scheme that works for general graph and depends on the partition of the vertex set V (G) into two partite sets satisfying some conditions. We investigate the radio number of power of cycles (C r ), Toroidal Grids Tm,n. We present an algorithm which gives a radio coloring of a graph G. For an n-vertex graph the running time of this algorithm is O(n4 ).
Venue
PL-8
Speaker
Dr. Laxman Saha
Affiliation
Department of Mathematics, Balurghat College
Title
Graph Radio k-coloring Problems : Variations of Channel Assignment Problem