Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2021
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2106.07424 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Table of Contents:
- The radio $k$-chromatic number $rc_k(G)$ of a graph $G$ is the minimum integer $λ$ such that there exists a function $ϕ: V(G) \to \{0,1,\cdots, λ\}$ satisfying $|ϕ(u)-ϕ(v)| \geq k+1 - d(u,v)$, where $d(u,v)$ denotes the distance between $u$ and $v$. A considerable amount of attention has been given to find the exact values or providing polynomial time algorithms to determine $rc_k(G)$ for several basic graph families such as paths, cycles, trees, and powers of paths, usually for some specific values of $k$. In this article, we find the exact values of $rc_k(G)$ where $G$ is a power of a path with diameter strictly less than $k$. Our proof readily provides a linear time algorithm for assigning a radio $k$-coloring of $G$. Furthermore, our proof technique is a potential tool for solving the same problem for other classes of graphs having ``small'' diameters.