![Sample our Computer Science journals, sign in here to start your access, latest two full volumes FREE to you for 14 days]({"type":"image" , "src" : "/sda/5928/TOC-Subject-Sample-2021-Computer-Science.jpg"})
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.Footnote†
†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.
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.