Radio Number for Square Paths

Abstract

Let \(G\) be a connected graph. For any two vertices \(u\) and \(v\), let \(d(u, v)\) denote the distance between \(u\) and \(v\) in \(G\). The maximum distance between any pair of vertices is called the diameter of \(G\) and denoted by \(diam(G)\). A radio-labeling (or multi-level distance labeling) with span \(k\) for \(G\) is a function \(f\) that assigns to each vertex a label from the set \(\{0, 1, 2, \ldots, k\}\) such that the following holds for any vertices \(u\) and \(v\): \(|f(u) – f(v)| \geq diam(G) – d(u, v) + 1\). The radio number of \(G\) is the minimum span over all radio-labelings of \(G\). The square of \(G\) is a graph constructed from \(G\) by adding edges between vertices of distance two apart in \(G\). In this article, we completely determine the radio number for the square of any path.