Even Kernels

.GivenagraphG =(V,E), an even kernel is a nonempty independent subset V # # V , such that every vertex of G isadjacenttoanevennumber(possibly0) of vertices in V # . It is proved that the question of whether a graph has an even kernel is NP-complete. The motivation stems from combinatorial game theory. It is known that this question is polynomial if G is bipartite. We also prove that the question of whether there is an even kernel whose size is between two given bounds, in a given bipartite graph, is NP-complete. This result has applications in coding and set theory. 1 Introduction Even Kernel (EVEK). Given an undirected graph G =(V,E). Is there a nonempty independent subset V # # V such that every u # V has even degree with respect to V # ,i.e., u has an even number (possibly 0) of neighbors in V # ? Example.InthegraphdepictedinFig.1,thesubset{u 1 ,u 3 ,u 7 ,u 9 } is an even kernel. So is its subset {u 1 ,u 3 };andalso{u 2 ,u 4 ,u 5 ,u 6 ,u 8 } is an even kernel. Thu..