$k$-Distance Magic Labeling and Long Brush Graphs

Abstract

We define a labeling $f:$ $V(G)$ $\to$ $\{1,2,\dots ,n\}$ on a graph $G$ of order $n\ge 3$ as a \emph{$k$-distance magic} ($k$-DM) if ${\sum }_{w\in \partial N_k(u)}f(w)$ is a constant and independent of $u\in V(G)$ where $\partial N_k(u)$ = $\{v\in V(G):d(u,v)=k\}$, $k\in \mathbb{N}$. Graph $G$ is called a \emph{$k$-DM} if it has a $k$-DM labeling(L). Long Brush is a graph $G$ with $V(G)$ = $\{u_1,u_2,...,u_n,$ $v_1,v_2,...,v_m\}$, a path $P_n$ = $u_1$ $u_2$ . . . $u_n$ and $E(G)$ = $E(P_n)$ $\cup$ $\{u_1{v}_i:$ $i$ = 1 to $m\}$ $\cup$ $E(<v_1,v_2,...,v_m>)$, $m+n\ge 3$ and $m,n\in \mathbb{N}$. We denoted this graph by $L{P}_{n,m}$. In this paper, using partition techniques, we obtain families of $k$-DM graphs and prove that $(i)$ For $k,n\ge 3$, $m\ge 2$ and $k,m,n\in \mathbb{N}$, $L{P}_{n,m}$ is $k$-DM if and only if $m(m-1)\le 2n$ and $k$ = $n$; (ii) For every $k\in {\mathbb{N}}_0$ and a given $m\ge 2$, $L{P}_{\frac{m(m-1)}{2}+k,m}$ is a $(\frac{m(m-1)}{2}+k)$-DM graph; (iii) For $m\ge 3$, $L{P}_{1,m}$ = $K_1(u_1)+(K_{m_1}\cup K_{m_2}\cup ...\cup K_{m_x})$, $x\ge 2$, $1\le m_1\le m_2\le ...\le m_x$, $m_1+m_2+...+m_x$ = $m$, $m_1+m_2\ge 3$ and $m_1,m_2,...,m_x,x\in \mathbb{N}$, $L{P}_{1,m}$ is 2-DM if and only if $u_1$ is assigned with a suitable $j$ and $J_{m+1}\setminus \{j\}$ is partitioned into $x$ constant sum partites of orders $m_1,m_2,...,m_x$, $1\le j\le m+1$; (iv) For $m\ge 2$ if $L{P}_{2,m}$ contains two pendant vertices, then $L{P}_{2,m}$ is not a $2$-DM graph; (v) For $m\ge 2$ and $n\ge 3$, if $L{P}_{n,m}$ contains three pendant vertices, then $L{P}_{n,m}$ is not a $2$-DM graph; and (vi) for $m_1$ = 1 to 22, we obtain all possible values of $m$ for which $L{P}_{1,m}$ = $u_1+(K_{m_1}\cup K_{m_2})$ is 2-DM, $m_1\le m_2$, $m=m_1+m_2\ge 3$ and $m_1,m_2\in \mathbb{N}$.

arXiv comment25 pages