turkmath.org

Domination is a graph theory concept which has many applications in computer science such as resource allocation and coding theory. A dominating set in a graph $G$ is a set $S$ of vertices of $G$ such that every vertex of $G$ is either in $S$ or is adjacent to a vertex in $S$. A dominating set is minimal if it does not contain another dominating set. The first part of this talk covers two special graph classes: well-dominated and almost well-dominated graphs. While the term well-dominated was first introduced by Finbow et al. [1] for the graphs whose minimal dominating sets have the same cardinality, we introduce almost well-dominated graphs as graphs with only two different sizes of minimal dominating sets, where the difference between these two sizes is one. The second part of this talk will be a discussion on a different variant of domination called paired domination, which was put forward by Haynes and Slater [2].

[1] Finbow A., Hartnell B., Nowakowski R., (1988), “Well-dominated graphs: a collection of well-covered ones”, Ars Combinatoria, 25, 5–10.

[2] Haynes T. W., Slater P. J., (1998), “Paired-domination in graphs”, Networks, 32 (3), 199–206.