Paired Domination on Cactus Graphs

A set S⊆V is a dominating set of a graphG=(V,E) if every vertex not in S is adjacent to a vertex in S. A dominating set S of a graph G is called a paired-dominating set if the induced subgraph G[S] contains a perfect matching. The paired-domination problem is to find the paired-dominating set of a graph with minimum size. A block in a graph G is a maximal connected subgraph of G without cut vertices. A cactus graph is a connected graph in which each block is either an edge or a cycle. Any two simple cycles have at most one vertex in common. Cactus graph usually used to model wireless network in some situation, and paired-domination problem can be used to solve problems of resource allocation and backup. In this thesis, we provide a greedy method algorithm with O(n)-time for the paired-domination problem on cactus graphs.