Open-independent, open-locating-dominating sets: structural aspects of some classes of graphs

Let $G=(V(G),E(G))$ be a finite simple undirected graph with vertex set$V(G)$, edge set $E(G)$ and vertex subset $S\subseteq V(G)$. $S$ is termed\emph{open-dominating} if every vertex of $G$ has at least one neighbor in $S$,and \emph{open-independent, open-locating-dominating} (an $OLD_{oind}$-set forshort) if no two vertices in $G$ have the same set of neighbors in $S$, andeach vertex in $S$ is open-dominated exactly once by $S$. The problem ofdeciding whether or not $G$ has an $OLD_{oind}$-set has important applicationsthat have been reported elsewhere. As the problem is known to be$\mathcal{NP}$-complete, it appears to be notoriously difficult as we show thatits complexity remains the same even for just planar bipartite graphs ofmaximum degree five and girth six, and also for planar subcubic graphs of girthnine. Also, we present characterizations of both $P_4$-tidy graphs and thecomplementary prisms of cographs that have an $OLD_{oind}$-set.Comment: 18 pages, 5 figure