Key Generation in Cryptography Using Radio Path Coloring

Abstract

An $L(p_{1},~p_{2},~p_{3},~{\dots },~p_{m})$ - labeling of a graph $G$ is an assignment of positive integers to the vertices of $G$ such that the difference in the labels assigned to the vertices at distance $i$ should be at least $p_{i}$ . The particular case of $p_{1} = d, \,\,p_{2} = d-1, \,\,p_{3} = d-2, {\dots }, p_{d} = 1$ where $d$ is the diameter of the graph, was known as the radio labeling of $G$ . The minimum value of the maximum integer used in any feasible radio labeling of $G$ was called as radio number of $G$ denoted by $rn(G)$ . The idea of radio path coloring was conceived to ensure secure communication in networks. If there exists a path between each pair of vertices, such that, the labeling in that path is an $L(p_{1},\,\,p_{1}-1,\,\,p_{1}-2,\,\,{\dots },\,\,1)-$ labeling, then such a labeling was called an $L(p_{1},\,\,p_{1}-1,\,\,p_{1}-2,\,\,{\dots },\,\,1)-$ path coloring or a radio path coloring of $G$ . The minimum value of the largest label used in such a coloring was called as the radio path connection number. Earlier researchers have studied the case of $p_{1}=2$ for different classes of graphs. We focus on the more general case of $p_{1} \geq 3$ and obtain an upper bound on the radio connection number $k_{p_{1}c}(G)$ , of any semi-Hamiltonian graph $G$ . An algorithm to obtain the radio path coloring of a Semi-Hamiltonian graph $G$ is also discussed here and the same is used to generate keys for secure communication in cryptography.

Keywords

• Cryptography
• radio labeling
• path coloring