Consecutive Radio Labeling of Hamming Graphs

Graph labeling was first introduced by Rosa in 1966 [7]. Since then, numerous types of labeling have been subject to extensive study including vertex coloring, graceful labeling, harmonious labeling, $k$-radio labeling, and more. For a survey of graph labeling, see Gallian [3].

This paper will continue a portion of Niedzialomski’s work [6] on radio labeling Hamming graphs (which have strong connections to coding theory, see [1] and [9]), paying some attention to graphs of the form $K_{n}^{t}$. These graphs are defined via the Cartesian Product.

When discussing $G=K_{n}$, denote vertices with integer subscripts, $V(K_{n})=\{(v_{i})|i\in\mathbb{Z},1\leq i\leq n\}$. Denote any vertex $v\in V(K_{n}^{t})$ with the ordered $t$-tuple $(v_{i_{1}},v_{i_{2}},\ldots,v_{i_{t}})$ where $1\leq i_{j}\leq n$. When indexing is necessary for elements of $V(K_{n}^{t})$, we will use superscripts, e.g. $v^{i},v^{j}\in V(K_{n}^{t})$. As defined earlier, a vertex $v=(v_{i_{1}},v_{i_{2}},\ldots,v_{i_{j-1}},v_{i_{j}},v_{i_{j+1}},\ldots v_{i_{t}})$ is adjacent to every $(v_{i_{1}},v_{i_{2}},\ldots,v_{i_{j-1}},v_{i_{k}},v_{i_{j+1}},\ldots v_{i_{t}})$ where $i_{j}\neq i_{k}$. And so, if $v^{1}=(v_{i_{1}},v_{i_{2}},\ldots,v_{i_{t}})$ and $v^{2}=(v_{j_{1}},v_{j_{2}},\ldots,v_{j_{t}})$, then $d(v^{1},v^{2})$ is exactly the number of $k$ for which $i_{k}\neq j_{k}$. This shows that $K_{n}^{t}$ has diameter $t$.

This paper is primarily concerned with the more general Hamming graphs. Unless otherwise specified, the following conventions will be used throughout: $G=K_{n_{1}}^{t_{1}}\square\cdots\square K_{n_{m}}^{t_{m}}$ where $n_{1}<n_{2}<\cdots<n_{m}$. We let $\overline{t}_{k}:=\sum_{i=1}^{k}t_{i}$, and denote vertices $v\in V(G)$ by ordered $t$-tuples $v=(v_{i_{1}},\ldots,v_{i_{t}})$ where if $j$ is such that $\overline{t}_{k-1}<j\leq\overline{t}_{k}$, then $v_{i_{j}}\in V(K_{n_{k}})$. That is to say, the first $t_{1}$ coordinates are from $V(K_{n_{1}})$ and the next $t_{2}$ are from $V(K_{n_{2}})$ and so on. And just as in the case above, we have that the distance between two vertices is the number of coordinates in which the vertices differ. This also means that $G$ has diameter $\overline{t}_{m}$, which we will simply call $t$. Lastly, we let $N:=|V(G)|=\prod_{i=1}^{m}n_{i}^{t_{i}}$.

Niedzialomski has shown, by construction, that there exist optimal labelings (see Definition 4) for $K_{n}^{t}$ where $t\leq n$ (for $n\geq 3$) and there cannot exist such labelings when $t\geq 1+\frac{n(n^{2}-1)}{6}$. One goal of this paper is to work towards filling the gap where $n<t<1+\frac{n(n^{2}-1)}{6}$ depicted in Figure 2 taken from Niedzialomski’s paper.

Radio labeling comes from the Channel Assignment Problem of assigning frequencies to radio transmitters, where transmitters that are closer together, must have a bigger difference in frequency to avoid interference. This problem was introduced into graph theory by Hale in 1980 [5].

It is easy to see $k$-radio labeling as a generalization of some more familiar labelings. $1$-radio labeling is equivalent to vertex coloring since the radio condition for $k=1$ simply prohibits neighbors from having the same label. $2$-radio labeling is equivalent to $L(2,1)$-labeling which has also been studied quite heavily and was introduced in [4]. For a survey of $2$-labeling, see [8].

Radio labeling was originally introduced in [2]. This paper will only be concerned with consecutive radio labeling.

Ideally there would be an algorithm for quickly computing whether a general graph is radio graceful, but no efficient algorithm currently exists. Although the exact general computational complexity of this problem is unknown, the computation is too large for general graphs of even moderate size by any known algorithm. This paper will develop a method to more efficiently compute consecutive radio labelings of Hamming graphs, making use of Niedzialomski’s radio labelings induced by vertex orderings.

Given such an ordering, $O$, one can generate a radio labeling of $G$ by mapping $f(v^{1})=1$, and then mapping each vertex in order so that each vertex is sent to the smallest integer possible that still satisfies the radio condition. Put more formally,

Our goal is to generate orderings for Hamming graphs that induce consecutive radio labelings, or determine when this is not possible. In this section, we will restate the problem of finding consecutive radio labelings as an equivalent problem involving orderings. This will be accomplished via the following,

When $G=K_{n_{1}}^{t_{1}}\square\cdots\square K_{n_{m}}^{t_{m}}$, we will write any ordering, $O=(v^{1},\ldots,v^{N})$, as a $N\times t$ matrix where the $i$^th row of $O$ is $v^{i}=(v^{i}_{1},v^{i}_{2},\ldots,v^{i}_{t})$ where each $v^{i}_{j}=v_{l}\in V(K_{n_{k}})$ for some $l$ and the appropriate $n_{k}$. In particular, orderings of $K_{n}^{t}$ are $n^{t}\times t$ matrices containing elements from $V(K_{n})$ (See Figure 3). From now on, all orderings will be these matrices.

Proposition 7 allows us to essentially rewrite the radio condition in this new context of $N\times t$ matrices. This transforms our problem from graph labeling to trying to generate a matrix satisfying certain properties; namely, that row $i$ may be identical to row $i-k$ in at most $k-1$ places.

However, this transition from graph labeling to matrix generation means that we not only need to mind the radio condition but also avoid repetition as is mentioned in Proposition 7. Since our focus will almost always be on the radio condition with no regard for repetition, the following definition is necessary.

Lastly, the following definition and lemma will be helpful anytime we wish to relabel our $v_{i}$ in orderings.

One way to view the Cartesian product in this context is to see each coordinate of a vertex, and hence column of an ordering $O$, as corresponding to a copy of $K_{n_{l}}$ for some $l$, where each vertex (row) in the product is a choice of one vertex from each of these complete graphs of which there are $t$ in total. In light of this, the process of permuting a column as in Definition 10 is exactly the same as relabeling the vertices of the copy of $K_{n_{k}}$ to which this column corresponds. In general, this fact that each column is somewhat independent (as far as Proposition 7 is concerned) is what allows us to generalize many results from graphs of the form $K_{n}^{t}$ to more general Hamming graphs.

In Niedzialomski’s paper [6], it is shown that for any graph $G$, there is some integer $t$ for which $G^{t}$ is not radio graceful. Specifically there is a bound for $K_{n}^{t}$ stated here as Corollary 17. I will present an analogous bound for the more general case of Hamming Graphs. In the following proofs of bounds, we will consider orderings, and derive a contradiction if $t$ is too much larger than $n$.

I will demonstrate the idea behind the proof method of the bound with the example of $K_{3}^{5}$ which I will show to be not radio graceful. (It may be helpful to follow along in Figure 4)

See Figure 5 for a demonstration of this contradiction with $K_{4}^{11}$ (because $1+\frac{4(16-1)}{6}=11$), although this figure can also be viewed as a demonstration for $K_{3}^{4}\square K_{4}^{7}$.

The big idea is that because of the radio condition (viewed as in Proposition 7), we only have so many columns in which we can differ with previous vertices, so that many coordinates must be different from those above them and eventually this isn’t possible because we run out of options (i.e. elements of $V(K_{n})$).

With all of this under our belt, we are now ready to prove the bound. Note that the following corollary is found in ([6], Corollary 12) and this is simply a different and more direct proof (in that if $G=K_{n}^{t}$, i.e. $m=1$, then the following is a direct proof) using the construction above that is defined for the more general Hamming graphs.

Furthermore, we can by a similar method, using Definition 13, prove something constructive about graphs that are right underneath our bound.

Lastly, another result from Niedzialomski’s paper that I will not be showing here is that if $t\leq n$, then $G=K_{n}^{t}$ is radio graceful. She cleverly constructs a consecutive radio labeling using permutations of smaller segments of an ordering for $G$, but this construction does not give a consecutive radio labeling for $K_{n}^{n+1}$ so we must find a different approach to generating labelings in order to fill the gap in Figure 2.

Orderings have allowed us to restate the problem of radio labeling as one of constructing matrices that satisfy certain conditions. This abstraction not only makes the problem easier to reason about, especially with Hamming Graphs, but also leads us to certain results rather directly. In this section, I will introduce a new family of matrices that fully encapsulate radio labeling of Hamming Graphs in the hopes that this new paradigm will be helpful in finding new results and closing the gap in Figure 2. These new matrices can be viewed as containing ‘instructions’ for generating an ordering; however, we will often be able to restate the radio condition in the context of these generating matrices so that we need not consider orderings anymore, just as orderings allowed us to essentially disregard the graph concept.

Proposition 7 states the radio condition for orderings in such a way that allows us to view columns as somewhat independent, as has been mentioned earlier. In particular, if we are attempting to generate an ordering and we come to any entry, $v^{i}_{j}$, we need only inspect column $j$ when asking how this entry affects our radio condition considerations. As such, we will restrict ourselves to generating columns of orderings and find a mechanism for detecting repetition within a column, i.e. when two rows share a coordinate in this column.

We will construct a 1-1 correspondence between $A_{n}$ and $B_{n}$ using the following,

With this theorem, we are ready to restate the problem of radio labeling as a problem of finding matrices that generate orderings.

Notice that given any ordering that induces a consecutive radio labeling of $G$, we can always use Lemma 11 to get a new ordering whose first two rows are $(v_{1},\ldots,v_{1})$ and $(v_{2},\ldots,v_{2})$, as required above, that also induces a consecutive radio labeling.

The following is an example where an ordering of $K_{3}^{2}$ that induces a consecutive radio labeling is shown next to the its generator and intermediate construction where

is used for both columns. That is, the constant function $\Delta_{3}^{i}=\Delta_{3}$.

The reader is encouraged to write out their own example, even if it be just for a single column, and use this as reference later in this section and the next.

Now that we have the construction of order-generators, we wish to find a way of detecting repetition in the orderings that are generated.

In order to rewrite the conditions for a consecutive radio labeling more explicitly for $O^{\prime}$, we wish to keep track of when a run of instructions in a column of $O^{\prime}$ maps $1$ to itself, as this corresponds with repetition in that column of $O$ by the previous lemma.