Upper distance-two domination

Abstract

Let $G = (V, E)$ be a graph with vertex set $V$ and edge set $E$. A set $S \subset V$ is a $2$-packing in $G$ if for any two vertices $u,v \in S$, the distance between them satisfies $d(u,v) \gt 2$. The upper $2$-packing number $P_2(G)$ is the maximum cardinality of a $2$-packing in $G$. A set $S \subset V$ is a dominating set for $G$ if every vertex in $V - S$ is adjacent to at least one vertex in $S$. The domination number $\gamma(G)$ is the minimum cardinality of a dominating set in $G$. A set $S \subset V$ is a distance-$2$ dominating set if for every vertex $v \in V - S$ there exists a vertex $u \in S$ such that $d(u,v) \leq 2$. The upper distance-$2$ domination number $\Gamma_{\leq 2}(G)$ is the maximum cardinality of a minimal distance-$2$ dominating set in $G$. In this paper we establish two families of graphs $G$ for which $P_2(G) = \gamma(G) = \Gamma_{\leq 2}(G)$, which extend several well-known equalities of the form $P_2(G) = \gamma(G)$.