tailieunhanh - Báo cáo toán học: " EVEN KERNELS"

Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí toán học quốc tế đề tài: EVEN KERNELS. | EVEN KERNELS Aviezri Fraenkel1 Curtin University School of Mathematics and Statistics GPO Box U 1987 Perth WA 6001 Australia Abstract. Given a graph G V E an even kernel is a nonempty independent subset V c V such that every vertex of G is adjacent to an even number possibly 0 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 c V such that every u 2 V has even degree with respect to V . u has an even number possibly 0 of neighbors in V Example. In the graph depicted in Fig. 1 the subset u1 u3 u7 ug is an even kernel. So is its subset u1 u3 and also u2 u4 u5 u6 u8 is an even kernel. Thus an even kernel may exist nonuniquely. A triangle has no even kernel. 0 u u Figure 1. Even kernels in a graph G V E . The notion of an even kernel was defined in Fraenkel Scheinerman and Ullman 1993 1 Permanent address Dept. of Applied Mathematics and Computer Science The Weizmann Institute of Science Rehovot 76100 Israel. The main part of this work was done at the University of Pennsylvania and later at the University of Calgary during 1993. THE ELECTRONIC JOURNAL OF COMBINATORICS 1 1994 R5 2 with the motivation that the vertices of an even kernel are F-positions second player win positions in a game called Edge Geography . It was shown there that EK is polynomially decidable if G is bipartite. In 2 we prove Theorem 1. EVEK is NP-complete even for graphs with maximum degree 3. This result is best possible in the sense that for a graph with maximum degree 2 the question can be decided in linear time since