Labelling Algorithms for Paired-domination Problems in Block and Interval Graphs
| dc.creator | Zeng, Lei Chen Changhong Lu Zhenbing | |
| dc.date | 2008-02-20 | |
| dc.date.accessioned | 2026-07-07T09:21:55Z | |
| dc.date.available | 2026-07-07T09:21:55Z | |
| dc.description | Let $G=(V,E)$ be a graph without isolated vertices. A set $S\subseteq V$ is a paired-domination set if every vertex in $V-S$ is adjacent to a vertex in $S$ and the subgraph induced by $S$ contains a perfect matching. The paired-domination problem is to determine the paired-domination number, which is the minimum cardinality of a paired-dominating set. Motivated by a mistaken algorithm given by Chen, Kang and Ng [ Paired domination on interval and circular-arc graphs, Disc. Appl. Math. 155(2007),2077-2086], we present two linear time algorithms to find a minimum cardinality paired-dominating set in block and interval graphs. In addition, we prove that paired-domination problem is {\em NP}-complete for bipartite graphs, chordal graphs, even split graphs. | |
| dc.description | 15 pages | |
| dc.identifier | https://arxiv.org/abs/0802.2742 | |
| dc.identifier | http://arxiv.org/abs/0802.2742 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/155199 | |
| dc.subject | Combinatorics | |
| dc.subject | Optimization and Control | |
| dc.subject | 05C69; 05C85;68R10 | |
| dc.title | Labelling Algorithms for Paired-domination Problems in Block and Interval Graphs | |
| dc.type | text |