The Reduced Smith Group of a Kneser Graph and Its Application to Group-Valued Magic Maps

Source abstract

For a finite abelian group $Γ$, a map $f\colon V(G)\toΓ$ is a $Γ$-magic map if the sum of its values over the neighbors of a vertex is independent of the vertex. It is affinely generating if its pairwise differences generate $Γ$. When $|Γ|=|V(G)|$, a bijective $Γ$-magic map is a $Γ$-distance magic labeling. For a regular graph $G$ with adjacency matrix $A$, write $\mathbf1$ for the all-ones vector indexed by $V(G)$, and let $\overline A$ denote the endomorphism induced by $A$ on $Λ_{\mathbf1}=\mathbb Z^{V(G)}/\mathbb Z\mathbf1$. When $\overline A$ is nonsingular over $\mathbb Q$, define the reduced Smith group by $\mathsf S_{\mathrm{red}}(G)=\operatorname{coker}\overline A$. In previous work, we established that for every regular graph $G$ of positive degree with $\overline A$ nonsingular over $\mathbb Q$, one has $$G\text{ admits an affinely generating }Γ\text{-magic map} \quad\Longleftrightarrow\quad Γ\hookrightarrow\mathsf S_{\mathrm{red}}(G).$$ We determine this group explicitly for Kneser graphs. If $r\ge1$, $n\ge2r$, and $m_j=\binom nj-\binom n{j-1}$, then $$\mathsf S_{\mathrm{red}}(K(n,r))\cong \bigoplus_{j=1}^{r} \left(\mathbb Z/\binom{n-r-j}{r-j}\mathbb Z\right)^{m_j}.$$ When the labeling group and the Kneser graph have the same order, the resulting embedding criterion leaves only one case in which an affinely generating map exists. More precisely, if $Γ$ is an abelian group of order $\binom nr$, then $K(n,r)$ admits an affinely generating $Γ$-magic map if and only if $(n,r)=(9,2)$ and $Γ\cong\mathbb Z/6\mathbb Z\oplus\mathbb Z/6\mathbb Z$. A weak-Sidon-set bound shows that the affinely generating maps in the exceptional case cannot be bijective. Hence $K(n,r)$ admits no $Γ$-distance magic labeling throughout the range $r\ge1$ and $n\ge2r$.