Thesis (BS Applied Mathematics) -- University of the Philippines Mindanao, 2003

A set of vertices of a graph G=(V,E) is a dominating set if all the vertices/nodes in the graph are either in the set or neighbors of the vertices/nodes in the set. The main concern of this study is to an efficient algorithm for determining the minimum dominating set of the product graph of a path of order 2 and a cycle of length m ≥ 3 (P2 x Cm). The minimum dominating set of the graph P2 x Cm for all the values of m can be easily identified by enumerating all the possible states sequence. But for large values of m, it is tedious to enumerate all the possible states sequence. Using the approach of dynamic programming, a solution is produced with much less effort than exhaustive enumeration. A computer program is written to determine the sequence of states and its corresponding weight. Thus a cost matrix is obtained using the approach of dynamic programming wherein the elements of Cm(i, j) in row I and column j contain the quantities c(i, j) and f(i, j). from the cost matrix, the state sequence for any m is now obtainable. Thus, a minimum dominating set of P2 x Cm can be provided.