seminar

 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 ).