The Radio Antipodal and Radio Numbers of the Hypercube

Riadh Khennoufa1, Olivier Togni1
1 LE2I, UMR CNRS 5158 Université de Bourgogne, 21078 Dijon cedex, France

Abstract

A radio \(k\)-labeling of a connected graph \(G\) is an assignment \(f\) of non-negative integers to the vertices of \(G\) such that

\[|f(x) – f(y)| \geq k + 1 – d(x, y),\]

for any two vertices \(x\) and \(y\), where \(d(x, y)\) is the distance between \(x\) and \(y\) in \(G\). The radio antipodal number is the minimum span of a radio \((diam(G) – 1)\)-labeling of \(G\) and the radio number is the minimum span of a radio \((diam(G))\)-labeling of \(G\).

In this paper, the radio antipodal number and the radio number of the hypercube are determined by using a generalization of binary Gray codes.