Mathematics Graduate Students Organization

Seminar:

Date: October 16

Given a simple, undirected graph G, a subset D of vertices of G is called a dominating set if every vertex of G that is not an element of D is adjacent to an element of D. The domination number of G is the minimum cardinality for any dominating set for G, and the corresponding decision problem (i.e., given a graph G and input K, determine if the domination number of G <= K) is a classical NP-complete problem. In this talk I will discuss the total number of dominating sets of a graph, and give some simple lower and upper bounds for the domination number. I will also introduce a few other graph invariants related to domination, such as the star cover number, domatic number, independence number, and (time permitting) the total domination, connected domination and k-domination numbers. Finally, I will mention Vizing's Conjecture for the domination number of a Cartesian product of graphs.