Linear-time algorithm for the matched-domination problem in cographs

Abstract

Let G=(V, E) be a graph without isolated vertices. A matching in G is a set of independent edges in G. A perfect matching M in G is a matching such that every vertex of G is incident to an edge of M. A set S⊆ V is a paired-dominating set of G if every vertex not in S is adjacent to a vertex in S and if the subgraph induced by S contains a perfect matching. The paired-domination problem is to find a paired-dominating set of G with minimum cardinality. This paper introduces a generalization of the paired-domination problem, namely, the matched-domination problem, in which some constrained vertices are in paired-dominating sets as far as they can. Further, possible applications are also presented. We then present a linear-time constructive algorithm to solve the matched-domination problem in cographs.†

^†A preliminary version of this paper has appeared in: Proceedings of the 4th IASTED International Conference on Computational Intelligence (CI’2009), Honolulu, Hawaii, USA, 2009, pp. 120–126.

Keywords:

• graph algorithm
• paired-domination
• constrained vertex set
• matched-domination
• cographs

2010 AMS Subject Classifications :

• 05C69
• 05C85
• 68Q25

Acknowledgements

The authors would like to thank anonymous referees for many comments and suggestions which have improved the presentation of this paper. This work was partly supported by the National Science Council of Taiwan, R.O.C. under grant no. NSC98-2221-E-324-018.

Notes

^†A preliminary version of this paper has appeared in: Proceedings of the 4th IASTED International Conference on Computational Intelligence (CI’2009), Honolulu, Hawaii, USA, 2009, pp. 120–126.