Abstract: A set D of vertices in a graph G is a dominating set if every vertex of G not in D has a neighbor in D. The size of a smallest dominating set, denoted \gamma(G), is the domination number of G. We report on recent results with N. Ananchuen, with X. Zha, and with K. Kawarabayashi and A. Saito about three different topics involving domination in graphs.
A graph G is \gamma-edge-critical if \gamma(G+e)<\gamma(G) for each edge e\notin E(G). It is \gamma-vertex-critical if \gamma (G-v)<\gamma(G) for every vertex v\in V(G). The structure of \gamma-edge-critical graphs and \gamma-vertex-critical graphs is not well understood, even when \gamma(G)=3. We present new results on both classes that involve matchings.
In 1996, Matheson and Tarjan proved that a triangulated disc with n vertices has domination number at most n/3, and thus so does every n-vertex triangulation. We will present recent work toward extending this result to graphs of higher genus.
Reed conjectured in 1996 that if G is a cubic graph with n vertices, then \gamma (G) <= \lceil|V(G)|/3\rceil. This conjecture was very recently shown to be false by Kostochka and Stodolsky. We will close by discussing new results pertaining to this conjecture.