tailieunhanh - Báo cáo toán học: "Sudoku Graphs are Integral"

Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: Sudoku Graphs are Integral. | Sudoku Graphs are Integral Torsten Sander Institut fur Mathematik Technische Universitat Clausthal D-38678 Clausthal-Zellerfeld Germany e-mail Submitted Mar 1 2009 Accepted Jul 1 2009 Published Jul 24 2009 Mathematics Subject Classification Primary 05C50 Secondary 15A18 Abstract Sudoku graphs have only 5 or 6 distinct eigenvalues and all of them are integers. Moreover the associated eigenspaces admit bases with entries from the set 0 1 -1 . Keywords Sudoku integral graph graph spectrum 1 Introduction The recreational game of Sudoku has attained quite some popularity in recent years. A traditional Sudoku puzzle consists of a 3 X 3 arrangement of square blocks consisting of 3 X 3 cells each. Each cell may be empty or contain a number ranging from 1 to 9 see Figure 1. The aim of the puzzle is to fill the empty cells with numbers from 1 to 9 such that every row column and block of the puzzle contains all of the numbers 1 . 9. A properly set up Sudoku puzzle permits only one unique way of filling the missing numbers. Many different solution techniques exist for Sudoku puzzles 6 . The game can be generalised to n4 instead of 34 81 cells so that numbers from 1 to n2 need to be filled in. Let us call these puzzles n-Sudokus. As a result of Sudoku s general popularity there has also been an increasing amount of mathematical research on it. In particular the puzzle exhibits a close connection to graph theory. Given an empty n-Sudoku puzzle the corresponding Sudoku graph Sud n on n4 vertices is derived by establishing a one-to-one mapping between the vertices and the cells and adding edges between vertices if and only if the corresponding cells are situated in the same row column or block. This process is depicted in Figure 2. Numbers in the cells of an n-Sudoku puzzle can be interpreted as a vertex colouring THE ELECTRONIC JOURNAL OF COMBINATORICS 16 2009 N25 1 9 2 1 8 5 7 3 1 6 4 6 5 4 7 3 2 5 1 6 7 4 8 6 3 5 1 9 3 5 8 6 2 8 1 9 2 1 7 3 2