Computation of minimum dominating set for the graph C3 x Cm /
Julius B. Villano
- 2004
- 71 leaves
Thesis (BS Applied Mathematics) -- University of the Philippines Mindanao, 2004
Let G = (V,E) be an undirected graph, where V is the set of vertices in G and E is the set of edges in G. a dominating set S of a graph G is a subset of the set of vertices V such that every vertex in V is adjacent to at least one vertex in S. the subset with the least number of elements is called the minimum dominating set. This study is concerned about the computation of minimum dominating set of the product graph of two cycles, C3 x Cm. Several motivations for studying minimum dominating set of the graph C3 x Cm arises from wireless communication networks and resource allocation in distributed systems. However, this study can be applied only if the geographical properties of the data are somewhat similar to the graph of C3 x Cm. It reduces routing and searching process, minimizes operational costs, but at the same time provides convenience to consumers or subscribers. Using the properties of finite state spaces and backward dynamic programming and with the aid of a computer program, the final states that produces a minimum dominating set with the minimum cardinality y(G) for j 12 are identified. Furthermore, an algorithm is formulated for computation of minimum dominating set of C3 x Cm.