Unique Domination in Cross-Product Graphs

Joseph D. Masters
Department of Mathematics, University of Texas, Austin

Quentin F. Stout
Computer Science and Engineering, University of Michigan

Douglas M. Van Wieren
EECS Department, University of Michigan

Abstract: We present a method for approaching general domination and covering questions, tailored for cross-product graphs, and demonstrate it for questions concerning the existence of perfect dominating sets and perfect error-correcting codes. Here, the definition of cross-product graphs can include families of cube-connected cycles, cube-connected cubes as well as families of hypercubes, tori, etc.

We introduce a condition, unique domination, which is closely related to many other domination properties. This condition survives many variations in the notion of domination and can be explicitly determined for any arbitrary finite graph. Considering the regularities which exist in many families of cross-product graphs, the existence of this condition can often be demonstrated for all the members with only simple methods. Our approach to questions of domination relies on combining proofs of the unique domination condition with other tools. Adding only a simple graph projection technique, we demonstrate short proofs of necessary conditions for the existence of perfect dominating sets in selected examples of cross-product graphs.

Keywords: coverings, product graph, cross-product, dominating set, unique domination, grid graph, perfect dominating set, perfect error-correcting code, torus, cube-connected cycles, graph theory, discrete mathematics

Complete paper. This paper appears in Congressus Numerantium 118 (1996), pp. 49-71.

Related Work: here are my papers in graph theory and in parallel computing. Keywords are included so that you can search for relevant papers.