On the domination number of the generalized Petersen graphs

Graph domination numbers and algorithms for finding them have been investigated for numerous classes of graphs, usually for graphs that have some kind of tree-like structure. By contrast, we study an infinite family of regular graphs, the generalized Petersen graphs G(n)G(n). We give two procedures that between them produce both upper and lower bounds for the (ordinary) domination number of G(n)G(n), and we conjecture that our upper bound ⌈3n/5⌉⌈3n/5⌉ is the exact domination number. To our knowledge this is one of the first classes of regular graphs for which such a procedure has been used to estimate the domination number.