DOMINATION NUMBERS OF PLANAR GRAPHS

The problem of determining the domination number of a graph is a well known NP-hard problem, even when restricted to planar graphs. By addin g a further restriction on the diameter of the graph, we prove that pl anar graphs with diameter two and three have bounded domination number s. This implies that the domination number of such a graph can be dete rmined in polynomial time. We also give examples of planar graphs of d iameter four, and nonplanar graphs of diameter two, having arbitrarily large domination numbers. (C) 1996 John Wiley & Sons, Inc.