Radio Labeling of Path Graphs to the 6th Power


Reyna Hernandez, Edward Melendez, Jesus Mora, Cynthia Salgado


Min-Lin Lo, Mathematic Professor , Cal State San Bernardino

Radio labeling is a process used to model the problem of efficiently assigning channels to FM radio stations to avoid interference. Let $G$ be a connected graph. For any two vertices $u$ and $v$, the distance, $d(u,v)$, between $u$ and $v$ in $G$ is the length of the shortest $u-v$ path in $G$. The maximum distance between any pair of vertices of $G$ is called the diameter of $G$, $diam(G)$. A radio-labeling of $G$ is a function $f$ that assigns a label from the set $\left\{0, 1, 2, ...\right\}$ to each vertex such that the following holds for any vertices $u$ and $v$: $|f(u)-f(v)| \geq diam(G)-d(u,v)+1$. The span of $f$ is defined as $max_{u,v\in G}⁡\left\{|f(u)-f(v)| \right\}$. The radio number of $G$ is the minimum span among all radio-labelings of $G$. The 6th power of $G$ is a graph constructed from $G$ by adding edges between vertices of distance six or less apart in $G$. In this presentation we will discuss the progress we made towards finding the radio number for 6th power of paths during a 2013 MAA summer research program funded by NSA (grant H98230-13-1-0270) and NSF (grant DMS-1156582)

Presented by:

Jesus Mora, Reyna Hernandez, Edward Melendez


Saturday, November 23, 2013




Poster Session 1 - Villalobos Hall

Presentation Type:

Poster Presentation