Labelling Algorithms for Paired-domination Problems in Block and Interval Graphs

Details Labelling Algorithms for Paired-domination Problems in Block and Interval Graphs Labelling Algorithms for Paired-domination Problems in Block and Interval Graphs

2008-02-20

arxiv.org/abs/0802.2742v1

Mathematics

Combinatorics

15 pages

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Labelling Algorithms for Paired-domination Problems in Block and Interval Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Labelling Algorithms for Paired-domination Problems in Block and Interval Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Labelling Algorithms for Paired-domination Problems in Block and Interval Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-647015