Multi-Level Distance Labelings for Helm Graphs

Abstract

For a graph $G$ and any two vertices $u$ and $v$ in $G$, let $d_G(u,v)$ denote the distance between them and let $diam(G)$ be the diameter of $G$. A multi-level distance labeling (or radio labeling) for $G$ is a function $f$ that assigns to each vertex of $G$ a positive integer such that for any two distinct vertices $u$ and $v$, $d_G(u,v)+|f(u)–f(v)|=diam(G)+1$. The largest positive integer in the range of $f$ is called the span of $f$. The radio number of $G$, denoted $rn(G)$, is the minimum span of a multi-level distance labeling for $G$.

A helm graph $H_n$ is obtained from the wheel $W_n$ by attaching a vertex of degree one to each of the $n$ vertices of the cycle of the wheel. In this paper, the radio number of the helm graph is determined for every $n\ge 3$: $rn(H_3)=13$, $rn(H_4)=21$, and $rn(H_n)=4n+2$ for every $n\ge 5$. Also, a lower bound of $rn(G)$ related to the length of a maximum Hamiltonian path in the graph of distances of $G$ is proposed.