000			01777nam a2200241 4500
001			UPMIN-00000009074
003			UPMIN
005			20221205162819.0
008			221205b |||||||| |||| 00| 0 eng d
040			_aDLC _cUPMin _dupmin
041			_aeng
090			_aLG993.5 2003 _bA64 C83
100	1		_aCubio, Kristine Marie S. _9391
245	0	0	_aMinimum dominating set of graph P2 X Cm / _cKristine Marie S. Cubio
260			_c2003
300			_a57 leaves
502			_aThesis (BS Applied Mathematics) -- University of the Philippines Mindanao, 2003
520	3		_aA 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.
658			_aUndergraduate Thesis _cAMAT200
905			_aFi
905			_aUP
942			_2lcc _cTHESIS
999			_c153 _d153