Locating-Domination in Complementary Prisms

Abstract

Let $G=(V,E)$ be a graph and $\overline{G}$ be the complement of $G$. The complementary prism of $G$, denoted $G\overline{G}$, is the graph formed from the disjoint union of $G$ and $\overline{G}$ by adding the edges of a perfect matching between the corresponding vertices of $G$ and $\overline{G}$. A set $D\subseteq V(G)$ is a locating-dominating set of $G$ if for every $u\in V(G)\setminus D$, its neighborhood $N(u)\cap D$ is nonempty and distinct from $N(v)\cap D$ for all $v\in V(G)\setminus D$ where $v\ne u$. The locating-domination number of $G$ is the minimum cardinality of a locating-dominating set of $G$. In this paper, we study locating-domination of complementary prisms. We determine the locating-domination number of $G\overline{G}$ for specific graphs $G$ and characterize the complementary prisms with small locating-domination numbers. We also present upper and lower bounds on the locating-domination numbers of complementary prisms, and we show that all values between these bounds are achievable.