Subset of nodes such that all nodes of a graph are adjacent
In the literature, such a subset is called a perfect code.
As it is NP-complete to determine if a given graph has a perfect code, even on some very restricted inputs, your exponential-time algorithm is probably about as good as it gets.