The even adjacency split problem for graphs

The even adjacency split problem is defined as follows: given an undirected graph, determine whether its vertex set can be partitioned into two domina ting sets whose sizes differ by at most one. We show that the problem is NP -complete for general graphs. We also present two algorithms for restricted classes of graphs: first, an algorithm with time complexity linear in the number of edges that finds such a partition for all graphs which contain no isolated vertices and no vertex adjacent to more than two vertices of degr ee one; and second, an algorithm which determines if such a partition exist s for a tree with n vertices in time O(n(2)). (C) 2000 Elsevier Science B.V . All rights reserved.