Cylindrical Grid Graphs $P_m\square C_n$ are Non-Distance Magic

Abstract

A bijective mapping $f:V(G)\to \left\{1,2,\dots ,n\right\}$ is called a \emph{Distance Magic Labeling (DML) of $G$} if ~ ${\sum }_{v\in N(u)}f(v)$ is a constant for all $u\in V(G)$ where $G$ is a simple graph of order $n$ and $N(u)$ = $\{v\in V(G):$ $uv\in E(G)\}$. Graph $G$ is called a \emph{Distance Magic Graph (DMG)} if it has a DML, otherwise it is called a \emph{Non-Distance Magic (NDM) graph}. In 1996, Vilfred proposed a conjecture that cylindrical grid graphs $P_m\square C_n$ are NDM for $m\ge 2$, $n\ge 3$ and $m,n\in \mathbb{N}$. Recently, the authors could prove the conjecture for the case when $m$ is even by introducing neighbourhood chains of Type-1 (NC-T1) and Type-2 (NC-T2). In this paper, they introduce neighbourhood chains of Type-3 (NC-T3) and using them completely settle the conjecture and also identify families of NDM graphs.

arXiv admin note: substantial text overlap with arXiv:2303.11985