Minimum dominating set of P4 x Cm, M_>3 /
Kristine Joy P. Aro
- 2010
- 52 leaves.
College of Science and Mathematics
Thesis (BS Applied Mathematics) -- University of the Philippines Mindanao, 2010
In computer science and mathematics, we use diagrams in order to solve problems. 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 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 with the least number of elements is called the minimum dominating set. This study could be used in solving problems such as the computation of wireless network problems, reconstructing the evolutionary history of biological species, resource allocation and many more. In resource allocation, it helps a lot to minimize the operational costs while in communication networks, it helps provide reliable services. The objective of the study is to find the minimum dominating set of graphs P4 x Cm by partitioning of graph P4 x Cm into subgraphs P4 x P2 or P4 x P3. However, by partition of graph into subgraph, it came up a formula that could be easily used to find the minimum dominating set of graphs P4 x Cm, m≥ 3. If m is even, express two or more P4 x P2, then a domination number of graph P4 x Cm is m. If m is odd, express one (P4 x P3) and two or more (P4 x P2), then a domination number of graph P4 x Cm is m+1 if m is 3, 5, 9 and m ε Z+ While if m is 7, m ≥11 and m ε Z+, then the domination number of P4 x Cm is m
Cycle Minimumdominating set NP-complete Partition Path Product graph subgraphs