Paper Info
Title
Dominating Induced Matching In Some Subclasses Of Bipartite Graphs
Abstract
Given a graph G = (V, E), a set M subset of E is called a matching in G if no two edges in M share a common vertex. A matching M in G is called an induced matching if G[M], the subgraph of G induced by M, is same as G[S], the subgraph of G induced by S = {v is an element of V vertical bar v is incident on an edge of M}. An induced matching M in a graph G is dominating if every edge not in M shares exactly one of its endpoints with a matched edge. The dominating induced matching (DIM) problem (also known as Efficient Edge Domination) is a decision problem that asks whether a graph G contains a dominating induced matching or not. This problem is NP-complete for general graphs as well as for bipartite graphs. In this paper, we show that the DIM problem is NP-complete for perfect elimination bipartite graphs and propose polynomial time algorithms for star-convex, triad-convex and circular-convex bipartite graphs which are subclasses of bipartite graphs.
Year
DOI
Venue
2019
10.1007/978-3-030-11509-8_12
ALGORITHMS AND DISCRETE APPLIED MATHEMATICS, CALDAM 2019
Keywords
DocType
Volume
Matching, Dominating induced matching, Graph algorithms, NP-completeness, Polynomial time algorithms
Conference
11394
ISSN
Citations 
PageRank 
0302-9743
0
0.34
References 
Authors
0
2
Name
Order
Citations
PageRank
B. S. Panda19921.18
Juhi Chaudhary211.70