Multi-level and antipodal labelings for certain classes of circulant graphs

NEW

Problem: Reconstructed conjecture: for positive integers $k$ and even positive integers $m$, let

be the undirected circulant graph on $\mathbb Z_{4mk+2m}$, with $x\sim y$ iff $x-y\equiv \pm1,\pm2m\pmod{4mk+2m}$. Its radio number $\operatorname{rn}(G)$ is conjectured to equal the displayed two-case formula. This is the standard reading of the paper’s notation; the only visible typo is the missing parenthesis in $\operatorname{rn}(G(\cdots))$.

Result: The conjecture is false as stated.

Indeed, for every even $m$, the right-hand side is not an integer. If $k$ is odd, then

is odd, since all terms except $-k$ are even. If $k$ is even, then

is odd, since all terms except $-1$ are even. Hence the conjectured value is always a half-integer, while any radio number is an integer.

A concrete counterexample is $m=2,\ k=1$. Then $G=G(12;\{1,4\})$, and the conjectured value is

But $\operatorname{rn}(G)\in \mathbb Z$, so equality is impossible.

Moreover, the natural “rounding” repair is also false: for $G(12;\{1,4\})$, one checks that $\operatorname{diam}(G)=3$, and the only distance-three pairs are antipodal pairs differing by $6$. Thus in any radio ordering, a gap $1$ can occur only between one of the six antipodal pairs, so at most six of the eleven consecutive label gaps are $1$; all others are at least $2$. Hence every radio labeling has span at least

The labeling, in increasing order of labels,

with labels

is a valid radio labeling of span $16$. Therefore $\operatorname{rn}(G(12;\{1,4\}))=16$, not $13$, $14$, or $27/2$.

Thus the stated even-$m$ conjecture is rigorously disproved.

Citation: No external citation used; the counterexample and verification are given above.