Source author record

Arti Pandey

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Discrete Mathematics

Catalog footprint

Research overview

2works

1topics

2close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2016arXiv

Some Algorithmic Results on Restrained Domination in Graphs

A set $D\subseteq V$ of a graph $G=(V,E)$ is called a restrained dominating set of $G$ if every vertex not in $D$ is adjacent to a vertex in $D$ and to a vertex in $V \setminus D$ . The \textsc{Minimum Restrained Domination} problem is to find a restrained dominating set of minimum cardinality. Given a graph $G$ , and a positive integer $k$ , the \textsc{Restrained Domination Decision} problem is to decide whether $G$ has a restrained dominating set of cardinality a most $k$ . The \textsc{Restrained Domination Decision} problem is known to be NP-complete for chordal graphs. In this paper, we strengthen this NP-completeness result by showing that the \textsc{Restrained Domination Decision} problem remains NP-complete for doubly chordal graphs, a subclass of chordal graphs. We also propose a polynomial time algorithm to solve the \textsc{Minimum Restrained Domination} problem in block graphs, a subclass of doubly chordal graphs. The \textsc{Restrained Domination Decision} problem is also known to be NP-complete for split graphs. We propose a polynomial time algorithm to compute a minimum restrained dominating set of threshold graphs, a subclass of split graphs. In addition, we also propose polynomial time algorithms to solve the \textsc{Minimum Restrained Domination} problem in cographs and chain graphs. Finally, we give a new improved upper bound on the restrained domination number, cardinality of a minimum restrained dominating set in terms of number of vertices and minimum degree of graph. We also give a randomized algorithm to find a restrained dominating set whose cardinality satisfy our upper bound with a positive probability.

preprint2015arXiv

Algorithmic aspects of disjunctive domination in graphs

For a graph $G=(V,E)$ , a set $D\subseteq V$ is called a \emph{disjunctive dominating set} of $G$ if for every vertex $v\in V\setminus D$ , $v$ is either adjacent to a vertex of $D$ or has at least two vertices in $D$ at distance $2$ from it. The cardinality of a minimum disjunctive dominating set of $G$ is called the \emph{disjunctive domination number} of graph $G$ , and is denoted by $γ_{2}^{d}(G)$ . The \textsc{Minimum Disjunctive Domination Problem} (MDDP) is to find a disjunctive dominating set of cardinality $γ_{2}^{d}(G)$ . Given a positive integer $k$ and a graph $G$ , the \textsc{Disjunctive Domination Decision Problem} (DDDP) is to decide whether $G$ has a disjunctive dominating set of cardinality at most $k$ . In this article, we first propose a linear time algorithm for MDDP in proper interval graphs. Next we tighten the NP-completeness of DDDP by showing that it remains NP-complete even in chordal graphs. We also propose a $(\ln(Δ^{2}+Δ+2)+1)$ -approximation algorithm for MDDP in general graphs and prove that MDDP can not be approximated within $(1-ε) \ln(|V|)$ for any $ε>0$ unless NP $\subseteq$ DTIME $(|V|^{O(\log \log |V|)})$ . Finally, we show that MDDP is APX-complete for bipartite graphs with maximum degree $3$ .

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.