Planar Domination Graphs
by
Elaine M. Eschen
West Virginia University
Coauthors: William F. Klostermeyer (University of North Florida), R. Sritharan (The University of Dayton)

A graph G is a domination graph if each induced subgraph H of G (with at least two vertices) has a pair of vertices v and u such that the open neighborhood of v is contained in the closed neighborhood of u in H. We say that the vertex v is a dominated vertex of H. No polynomial time algorithm or hardness result is known for the problem of deciding whether a graph is a domination graph. In this paper, it is shown that the class of planar domination graphs is equivalent to the class of planar weakly chordal graphs, and thus, can be recognized in polynomial time. We also prove that if G is a planar domination graph, then G either is a clique or has two nonadjacent dominated vertices.

Date received: April 18, 2001