An Integer Linear Programming Model for Solving Radio Mean Labeling Problem

A Radio mean labeling of a connected graph <inline-formula> <tex-math notation="LaTeX">$G$ </tex-math></inline-formula> is an injective function <inline-formula> <tex-math notation="LaTeX">$h$ </tex-math></inline-formula> from the vertex set, <inline-formula> <tex-math notation="LaTeX">$V(G)$ </tex-math></inline-formula>, to the set of natural numbers <inline-formula> <tex-math notation="LaTeX">$N$ </tex-math></inline-formula> such that for any two distinct vertices <inline-formula> <tex-math notation="LaTeX">$x$ </tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">$y$ </tex-math></inline-formula> of <inline-formula> <tex-math notation="LaTeX">$G$ </tex-math></inline-formula>, <inline-formula> <tex-math notation="LaTeX">$\left \lceil{ \frac {h\left ({x }\right)+h(y)}{2} }\right \rceil \mathrm {\ge }diam\mathrm {+1-}d(x,y)$ </tex-math></inline-formula>. The radio mean number of <inline-formula> <tex-math notation="LaTeX">$h$ </tex-math></inline-formula>, <inline-formula> <tex-math notation="LaTeX">$rmn(h)$ </tex-math></inline-formula>, is the maximum number assigned to any vertex of <inline-formula> <tex-math notation="LaTeX">$G$ </tex-math></inline-formula>. The radio mean number of <inline-formula> <tex-math notation="LaTeX">$G$ </tex-math></inline-formula>, <inline-formula> <tex-math notation="LaTeX">$rmn(G)$ </tex-math></inline-formula>, is the minimum value of <inline-formula> <tex-math notation="LaTeX">$rmn(h)$ </tex-math></inline-formula>, taken over all radio mean labeling <inline-formula> <tex-math notation="LaTeX">$h$ </tex-math></inline-formula> of <inline-formula> <tex-math notation="LaTeX">$G$ </tex-math></inline-formula>. This work has three contributions. The first one is proving two theorems which find the radio mean number for cycles and paths. The second contribution is proposing an approximate algorithm which finds an upper bound for radio mean number of a given graph. The third contribution is that we introduce a novel integer linear programing formulation for the radio mean problem. Finally, the experimental results analysis and statistical test proved that the Integer Linear Programming Model overcame the proposed approximate algorithm according to CPU time only. On the other hand, both the Integer Linear Programming Model and the proposed approximate algorithm had the same upper bound of the radio mean number of <inline-formula> <tex-math notation="LaTeX">$G$ </tex-math></inline-formula>.

Abstract licence: CC BY-NC-ND

A person counts once a day per paper. We keep no cookie and no address: a reader is a hash that changes every day. Any month under five reads shows no number.