Abstract |
Let $G=(V,E)$ be a simple connected graph of order $n$. Let $d_G(u, v)$ denote the distance, i.e., the shortest length of all paths between the two vertices $u$ and $v$ in $G$. And let $\mbox{diam}(G)$ denote the diameter, i.e., the largest distance between any pair of distinct vertices in $G$. A \textit{radio labeling} for $G$ is a function $f$ from $V$ to $\mathbf{N}$, the set of all natural numbers, such that $|f(u)-f(v)| \geq \mbox{diam}(G)+1-d_G(u, v)$ holds for any two distinct vertices $u$ and $v$ of $G$. The maximum number in $f(V)$ is called the span of $f$. The \textit{radio number} of $G$, denoted by $rn(G)$, is the minimum span among all radio labelings for $G$. The \textit{$3$rd power} of a graph $G$, denoted by $G^3$, is a graph constructed from $G$ by adding the edges between vertices whose distance from each other are two and three in $G$. Furthermore, for a positive integer $k$ and $1 \leq k \leq n-1$, the \textit{$k$-th power} of $G$, denoted by $G^k$, is a graph constructed from $G$ by adding the edges between vertices whose distance from each other are less than or equal to $k$ in $G$. In this thesis, we almost completely determine the radio numbers of the $3$rd powers of paths, $P_n^3$. For the radio numbers of the $k$-th powers of paths, $P_n^k$, we give lower bounds for them. |