Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4647597 | Discrete Mathematics | 2014 | 8 Pages |
Abstract
We discuss the problem of finding critical sets in graphs, a concept which has appeared in a number of guises in the combinatorics and graph theory literature. The case of the Sudoku graph receives particular attention, because critical sets correspond to minimal fair puzzles. We define four parameters associated with the sizes of extremal critical sets and (a) prove several general results concerning the properties of these parameters, including their computational intractability, (b) compute their values exactly for some classes of graphs, (c) obtain bounds for generalized Sudoku graphs, and (d) offer a number of open questions regarding critical sets and the aforementioned parameters.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Joshua Cooper, Anna Kirkpatrick,