On distance dominator packing coloring in graphs

Abstract

Let $G$ be a graph and let $S=(s_1, s_2, \ldots, s_k)$ be a non-decreasing sequence of positive integers. An {\em $S$-packing coloring} of $G$ is a mapping $c: V(G) \rightarrow \{1,2, \ldots, k\}$ with the following property: if $c(u)=c(v)=i$, then $d(u, v) > s_i$ for any $i \in \{1, 2, \ldots, k\}$. In particular, if $S=(1,2,3, \ldots, k)$, then $S$-packing coloring of $G$ is well known under the name \textit{packing coloring}. %The smallest integer $k$ such that there exists an packing coloring of $G$, is called the {\em packing chromatic number} of $G$ and is denoted by $\chi_{\rho}(G)$.
Next, let $r$ be a positive integer and $u, v \in V(G)$. A vertex $u$ \textit{$r$-distance dominates} a vertex $v$ if $d_G(u,v) \leq r$.

In this paper, we present a new concept of a coloring, namely \textit{distance dominator packing coloring}, defined as follows. A coloring $c$ is a \textit{distance dominator packing coloring} of $G$ if it is a packing coloring of $G$ and for each $x \in V(G)$ there exists $i \in \{1,2,3, \ldots\}$ such that $x$ $i$-distance dominates each vertex from the color class of color $i$. The smallest integer $k$ such that there exists a distance dominator packing coloring of $G$ using $k$ colors, is the \textit{distance dominator packing chromatic number} of $G$, denoted by $\chi_{\rho}^d(G)$.
In this paper, we provide some lower and upper bounds on the distance dominator packing chromatic number, characterize graphs $G$ with $\chi_{\rho}^d(G) \in \{2,3\}$, and provide the exact values of $\chi_{\rho}^d(G)$ when $G$ is a complete graph, a star, a wheel, a cycle or a path. In addition, we consider the relation between $\chi_\rho(G)$ and $\chi_{\rho}^d(G)$ for a graph $G$.