Multi-Level Distance Labelings for Helm Graphs

M. Tariq Rahim1, Ioan Tomescu2
1School of Mathematical Sciences, Government. College University, 68-B New Muslim Town, Lahore, Pakistan
2 Faculty of Mathematics and Computer Science, University of Bucharest, Str. Academiei, 14, 010014 Bucharest, Romania

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 \geq 3\): \(rn(H_3) = 13\), \(rn(H_4) = 21\), and \(rn(H_n) = 4n + 2\) for every \(n \geq 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.