Search

For $k \geq 1$, in a graph $G=(V,E)$, a set of vertices $D$ is a distance $k$-dominating set of $G$, if any vertex in $V\setminus D$ is at distance at most $k$ from some vertex in $D$. The minimum cardinality of a distance $k$-dominating set of $G$ is the distance $k$-domination number, denoted by $\gamma_k(G)$. An ordered set of vertices $W=\{w_1,w_2,\ldots,w_r\}$ is a resolving set of $G$, if for any two distinct vertices $x$ and $y$ in $V\setminus W$, there exists $1\leq i\leq r$, such that $d_G(x,w_i)\neq d_G(y,w_i)$. The minimum cardinality of a resolving set of $G$ is the metric dimension of the graph $G$, denoted by $dim(G)$. In this paper, we introduce the distance $k$-resolving dominating set, which is a subset of $V$ that is both a distance $k$-dominating set and a resolving set of $G$. The minimum cardinality of a distance $k$-resolving dominating set of $G$ is called the distance $k$-resolving domination number and is denoted by $\gamma^r_k(G)$. We give several bounds for $\gamma^r_k(G)$ some in terms of the metric dimension $dim(G)$ and the distance $k$-domination number $\gamma_k(G)$. We determine $\gamma^r_k(G)$ when $G$ is a path or a cycle. Afterwards, we characterize the connected graphs of order $n$ having $\gamma^r_k(G)$ equal to $1$, $n-2$, and $n-1$, for $k\geq 2$. Then, we construct graphs realizing all the possible triples $(dim(G),\gamma_k(G),\gamma^r_k (G))$, for all $k\geq 2$. Later, we determine the maximum order of a graph $G$ having distance $k$-resolving domination number $\gamma^r_k(G)=\gamma^r_k\geq 1$, we provide graphs achieving this maximum order for any positive integers $k$ and $\gamma^r_k$. Finally, we establish Nordhaus-Gaddum bounds for $\gamma^r_k(G)$, for $k\geq 2$.

In this paper, we study the $L(2, 1)$-Labeling of the Mycielski and the iterated Mycielski of graphs in general. For a graph $G$ and all $t\geq 1$, we give sharp bounds for $\lambda(M^t(G))$ the $L(2, 1)$-labeling number of the $t$-th iterated Mycielski in terms of the number of iterations $t$, the order $n$, the maximum degree $\bigtriangleup$, and $\lambda(G)$ the $L(2, 1)$-labeling number of $G$. For $t=1$, we present necessary and sufficient conditions between the $4$-star matching number of the complement graph and $\lambda(M(G))$ the $L(2, 1)$-labeling number of the Mycielski of a graph, with some applications to special graphs. For all $t\geq 2$, we prove that for any graph $G$ of order $n$, we have $2^{t-1}(n+2)-2\leq \lambda(M^t(G))\leq 2^{t}(n+1)-2$. Thereafter, we characterize the graphs achieving the upper bound $2^t(n+1)-2$, then by using the Marriage Theorem and Tutte's characterization of graphs with a perfect $2$-matching, we characterize all graphs without isolated vertices achieving the lower bound $2^{t-1}(n+2)-2$. We determine the $L(2, 1)$-labeling number for the Mycielski and the iterated Mycielski of some graph classes., Comment: 18 pages, 8 figures