Optimal radio labelings of the Cartesian product of the generalized Peterson graph and tree

Abstract

A radio labeling of a graph $G$ is a function $f:V(G)\to \{0,1,2,\dots \}$ such that $|f(u)-f(v)|\ge diam(G)+1-d(u,v)$ for every pair of distinct vertices $u,v$ of $G$. The radio number of $G$, denoted by $rn(G)$, is the smallest number $k$ such that $G$ has radio labeling $f$ with max$\{f(v):v\in V(G)\}=k$. In this paper, we give a lower bound for the radio number for the Cartesian product of the generalized Petersen graph and tree. We present two necessary and sufficient conditions, and three other sufficient conditions to achieve the lower bound. Using these results, we determine the radio number for the Cartesian product of the Peterson graph and stars.

15 pages, 1 figure