Title

On the Power Domination Problem in Graphs

Document Type

Thesis

Comments


Presented to the Honors Committee of Texas State University-San Marcos In Partial Fulfillment of the Requirements For Graduation in the University Honors Program, May, 2009
Thesis Advisor:
Dr. Daniela Ferrero

Abstract

A crucial task for electric power companies consists of the continuous monitoring of their power network. This monitoring can be efficiently accomplished by placing phase measurement units (PMUs) at selected network locations. However, due to the high cost of the PMUs, their number must be minimized [1]. Finding the minimum number of PMUs needed to monitor a given power network, as well as to determine the locations where the PMUs should be placed, give rise to the power domination problem in graph theory [8].

The power dominating problem is NP-complete, that is, there is no efficient way of finding a minimal power dominating set for a graph. However, closed formulas for the power domination number of certain families of graphs, such as rectangular grids [5] have been found.

AMS Subject Classification: 05C90, 05C69