School Seminars and Colloquia

Two domination parameters in graphs

Discrete Structures and Algorithms (Seminar)

by Guangjun Xu


Institution: Mathematics and Statistics Dept, The University of Melbourne
Date: Tue 30th June 2009
Time: 2:15 PM
Location: Room 107, Richard Berry Building, The University of Melbourne

Abstract: Let $G$ be a graph. A subset $S$ of $G$ is called a dominating set if every vertex not in $S$ has a neighbour in $S$. The cardinality of a minimum dominating set of $G$ is called the domination number of $G$. In this talk, I will introduce the concepts of power domination and $k$-rainbow domination in graphs.

Power domination arises from the power network monitoring problem, which seeks to place as few phase measurement units (PMUs) as possible at selected network locations such that the whole network can be monitored. I will present our results of power domination in block graphs.

Assume we have a set of $k$ colours and we assign an arbitrary subset of these colours to each vertex of a graph $G$. If we require that each vertex to which an empty set is assigned has in its neighborhood all $k$ colours, then this assignment is called a $k$-rainbow dominating function of $G $.
I will address the $2$-rainbow domination in the generalized Petersen graphs.

Joint work with L. Kang, E. Shan and M. Zhao.

For More Information: contact: David Wood. email: woodd@unimelb.edu.au