# Subset of nodes such that all nodes of a graph are adjacent

We have been given a graph $$G$$, we need to find a subset of nodes $$S$$ such that each node of the graph is in $$S$$ or is adjacent to a node from $$S$$. Additionally, the elements of the subset $$S$$ should not be adjacent to each other neither should they share a common neighbour node.

This is an example of the given problem: In the given graph, the subset $$S =$$ {2, 4} is a valid solution as $$3$$ and $$5$$ are adjacent to 2 while $$1$$ and $$6$$ are adjacent to $$4$$. Further, $$2$$ and $$4$$ are not adjacent neither do they share a common neighbour.

The subset $$S =$$ {4, 5} is NOT valid as $$4$$ and $$5$$ have a common neighbour $$1$$.

I have been looking for an efficient way to do this; my attempt at an algorithm gives an exponential time complexity.

Any hints are appreciated, thanks in advance.

• I'd start pondering distance and cuts. Mar 12 at 7:09
• @greybeard Could you elaborate a bit more? Mar 12 at 7:44
• Out of my turf here, but sure I can: needing all nodes covered exactly once, you need nodes at a pairwise distance of three. Within a single connected component of $G$, it may lead to a useful heuristic to consider the/a diameter. Pondering cuts got me nowhere. Mar 12 at 8:39