TAILIEUCHUNG - Báo cáo toán học: "Computing the Domination Number of Grid Graphs"

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í Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài: Computing the Domination Number of Grid Graphs. | Computing the Domination Number of Grid Graphs Samu Alanko Courant Institute of Mathematical Sciences New York University 251 Mercer Street New York . 10012-1185 . Simon Crevals Department of Communications and Networking Aalto University School of Electrical Engineering . Box 13000 00076 Aalto Finland Anton Isopoussu Department of Pure Mathematics and Mathematical Statistics Centre for Mathematical Sciences University of Cambridge Wilberforce Road Cambridge CB3 0WB UK United Kingdom aai22@ Patric Ostergard Department of Communications and Networking Aalto University School of Electrical Engineering . Box 13000 00076 Aalto Finland Ville Pettersson Department of Information and Computer Science Aalto University School of Science . Box 15400 00076 Aalto Finland Submitted Mar 2 2011 Accepted Jul 6 2011 Published Jul 15 2011 Mathematics Subject Classification 05C69 90C39 Abstract Let Ym n denote the size of a minimum dominating set in the m X n grid graph. For the square grid graph exact values for Yn n have earlier been published for n 19. By using a dynamic programming algorithm the values of Ym n for m n 29 are here obtained. Minimum dominating sets for square grid graphs up to size 29 X 29 are depicted. Supported by the Academy of Finland Grant No. 132122 and by the Finnish Foundation for Technology Promotion. Supported in part by the Academy of Finland Grants No. 130142 132122. THE ELECTRONIC JOURNAL OF COMBINATORICS 18 2011 P141 1 1 Introduction An m X n grid graph G has the vertex set V vij 1 i m 1 j n with two vertices vij and Wj being adjacent if i Ỉ and j j I 1 or if j j and i i 1. The m X n grid graph can also be presented as a Cartesian product Pm JPn of a path of length m 1 and a path of length n 1. A dominating set of a graph G V E is a subset V c V such that every vertex not in V is adjacent to at least one vertex in V . The .

• Báo cáo khoa học
• báo cáo của tạp chí Department of Mathematic
• tài liệu báo cáo nghiên cứu khoa học
• cách trình bày báo cáo
• kiến thức toán học
• báo cáo toán học