Open-independent, Open-locating-dominating Sets in Complementary Prism Graphs

For a finite, simple, undirected graph G = (V (G),E(G)), an open-dominating set S ⊆ V (G) is such that every vertex in G has at least one neighbor in S. An open-independent, open-locating-dominating set S ⊆ V (G) (OLDOIND-set for short) is such that no two vertices in G have the same set of neighbors in S and each vertex in S is open-dominated exactly once by S. The problem of deciding whether or not a given graph has an OLDOIND-set is known to be NP -complete. The complementary prism of G is the graph G G ‾ , formed from the disjoint union of G and its complement G ‾ by adding the edges of a perfect matching between the corresponding vertices of G and G ‾ . We provided a logarithmic lower bound on the size of an OLDOIND-set in any graph. Various properties of and bounds on OLDOIND-sets in complementary prisms were presented and the cases of cliques, paths and cycles have been completely solved. It has been shown that for any graph with girth at least five, it can be decided in polynomial time whether or not its complementary prism has an OLD-OIND-set (and also the set can be found in polynomial time if it exists).