Date of Award

Winter 2019

Document Type

Thesis

Degree Name

Master of Science (M.S.) in Mathematics

Department

Mathematics and Statistics

Subjects

Graph theory, Sudoku, Combinatorial analysis

Abstract

A sudoku puzzle is most commonly a 9 × 9 grid of 3 × 3 boxes wherein the puzzle player writes the numbers 1 - 9 with no repetition in any row, column, or box. We generalize the notion of the n2 × n2 sudoku grid for all n ϵ Z ≥2 and codify the empty sudoku board as a graph. In the main section of this paper we prove that sudoku boards and sudoku graphs exist for all such n we prove the equivalence of [3]'s construction using unions and products of graphs to the definition of the sudoku graph; we show that sudoku graphs are Cayley graphs for the direct product group Zn × Zn × Zn ×|Zn; and we find the automorphism group of the sudoku graph. In the subsequent section, we find and prove several graph theoretic properties for this class of graphs, and we offer some conjectures on these and other properties.

Comments

Mathematical literature project in partial fulfillment of requirements for the Master of Science in Mathematics

Under the direction of Dr. John Caughman with second reader Dr. Sean Larsen

Persistent Identifier

https://archives.pdx.edu/ds/psu/29970

Download

Share

COinS