Study on Power Domination of Graphs
Date Issued
2008
Date
2008
Author(s)
Chuang, Chien-Cheng
Abstract
Electric power companies monitor the state of their electric power system by placing phase measurement units (PMUs) at selected locations in the system. They want to place as few measurement devices as possible such that these devices still monitor the whole system. This problem can be considered as a variation of the domination problem in graph theory, which we call the power domination problem.ower domination problem is defined as follows: given a graph G, a subset S is called a power dominating set if every vertex of G can be observed by S by repeatedly applying the following rules: (i) vertices in S and their neighbors are observed; (ii) if at some stage an observed vertex has exactly one unobserved neighbor, then this neighbor is observed. The purpose of the problem is to find a minimum power dominating set S of G. The minimum cardinality of a power dominating set of G is called the power domination number $gamma_p(G)$.n this thesis, we first determine the power domination numbers of the Cartesian product of two cycles. We then investigate the properties of co-graphs and give an algorithm for the power domination problem on co-graphs. Finally, we present a labeling algorithm for the power domination problem on trees.
Subjects
domination
power domination
tree
cograph
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-97-R95221001-1.pdf
Size
23.53 KB
Format
Adobe PDF
Checksum
(MD5):d1587618e3b28c267268c7ffaf9e31f7