## Abstract

For a graph G with no isolated vertices, a dominating set D of G is called a semipaired dominating set of G if D can be partitioned into 2-element subsets such that the vertices in each 2-element set are at distance at most two. The minimum cardinality of a semipaired dominating set of G is called the semipaired domination number of G, and is denoted by pr2(G). The Minimum Semipaired Domination problem is to find a semipaired dominating set of G of cardinality pr2(G). Given a graph G and a positive integer k, the Semipaired Domination Decision problem is to decide whether G has a semipaired dominating set of cardinality at most k. In this paper, we show that the Semipaired Domination Decision problem is NPcomplete even for split graphs, an important subclass of chordal graphs. On the positive side, we propose a linear-time algorithm to solve the Minimum Semipaired Domination problem in trees.

Original language | English |
---|---|

Pages | 73-76 |

Number of pages | 4 |

Publication status | Published - 2019 |

Event | 17th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2019 - Enschede, Netherlands Duration: 1 Jul 2019 → 3 Jul 2019 |

### Conference

Conference | 17th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2019 |
---|---|

Country/Territory | Netherlands |

City | Enschede |

Period | 1/07/19 → 3/07/19 |

## Keywords

- Chordal graphs
- Domination
- Graph algorithms.
- NP-completeness
- Semipaired domination

## ASJC Scopus subject areas

- Control and Optimization
- Discrete Mathematics and Combinatorics