Paper Info
Title
Minimum paired-dominating set in chordal bipartite graphs and perfect elimination bipartite graphs
Abstract
A set D⊆V of a graph G=(V,E) is a dominating set of G if every vertex in V驴D has at least one neighbor in D. A dominating set D of G is a paired-dominating set of G if the induced subgraph, G[D], has a perfect matching. Given a graph G=(V,E) and a positive integer k, the paired-domination problem is to decide whether G has a paired-dominating set of cardinality at most k. The paired-domination problem is known to be NP-complete for bipartite graphs. In this paper, we, first, strengthen this complexity result by showing that the paired-domination problem is NP-complete for perfect elimination bipartite graphs. We, then, propose a linear time algorithm to compute a minimum paired-dominating set of a chordal bipartite graph, a well studied subclass of bipartite graphs.
Year
DOI
Venue
2013
10.1007/s10878-012-9483-x
J. Comb. Optim.
Keywords
Field
DocType
Perfect matching,Paired-domination,Chordal bipartite graphs,Perfect elimination bipartite graphs,NP-complete
Complete bipartite graph,Discrete mathematics,Dominating set,Combinatorics,Chordal graph,Chordal bipartite graph,Bipartite graph,Independent set,Mathematics,Maximal independent set,Strong perfect graph theorem
Journal
Volume
Issue
ISSN
26
4
1382-6905
Citations 
PageRank 
References 
5
0.41
19
Authors
2
Name
Order
Citations
PageRank
B. S. Panda19921.18
D. Pradhan2212.52