Finding Non-Distance Magic Graphs using neighbourhood chains

Abstract

Let $G$ be a graph of order $n$ and $N=\{N(u_i){\}}_{i=1}^k$ be a sequence of neighbourhood(nbh)s in $G$ where $N(u)$ = $\{v\in V(G):$ $uv\in E(G)\}$. \emph{Nbh sequence graph $H$ of} $N$ in $G$ is defined as the union of all induced subgraphs of closed nbh $N[u_i]$ in $G$, $1\le i\le k$, $k\in \mathbb{N}$. A labeling $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 every $u\in V(G)$. $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 this paper, we define nbh walk, nbh trial, nbh path or nbh chain, nbh cycle, nbh sequence graph and nbh chains of Type-1 (NC-T1) and Type-2 (NC-T2). NC-T2 is formed on two NC-T1 of same length. We prove that (i) for $k\ge 2$ and $n\ge 3$, cylindrical grid graph $P_k\square C_n$ contains NC-T2, $k,n\in \mathbb{N}$; (ii) graph containing NC-T1 of even length is NDM and (iii) partially settle a conjecture that graphs $P_m\square C_n$ are NDM when $n$ is even, $m\ge 2$, $n\ge 3$ and $m,n\in \mathbb{N}$.

15 pages