Minimum dominating set of (P3 x Cm) a product of path of length 2 and a cycle of length m /
Junie L. Bao
- 2003
- 53 leaves
Thesis (BS Applied Mathematics) -- University of the Philippines Mindanao, 20103
A set vertices of a graphs is called dominating set if every other vertex is adjacent to at least one vertex of the set. It is found out that it has an application in transmitting messages in wireless communication links and in resource allocation in distributed system, in resource allocation, it helps a lot to minimize the operational costs while in communication networks, it helps provide reliable services. The main concern of this study is to find the minimum dominating set of the product graph of path P3 and a cycle of length m, for all m ≥ 3 by using dynamic programming. Using the approach in dynamic programming, an 11x11 cost matrix is produced through a computer program. From this cost matrix, a periodic behavior is observed to generate the state sequences. These state sequences produce the minimum dominating set of P3 x Cm.