# Convex and isometric domination of (weak) dominating pair graphs

Research paper by **Boštjan Brešar, Tanja Gologranc, Tim Kos**

Indexed on: **27 Apr '17**Published on: **27 Apr '17**Published in: **arXiv - Mathematics - Combinatorics**

Join Sparrho today to stay on top of science

Discover, organise and share research that matters to you

Join Sparrho today to stay on top of science

Discover, organise and share research that matters to you

Join for free

#### Abstract

A set $D$ of vertices in a graph $G$ is a dominating set if every vertex of
$G$, which is not in $D$, has a neighbor in $D$. A set of vertices $D$ in $G$
is convex (respectively, isometric), if all vertices in all shortest paths
(respectively, all vertices in one of the shortest paths) between any two
vertices in $D$ lie in $D$. The problem of finding a minimum convex dominating
(respectively, isometric dominating) set is considered in this paper from
algorithmic point of view. For the class of weak dominating pair graphs
(i.e.,~the graphs that contain a dominating pair, which is a pair of vertices
$x,y\in V(G)$ such that vertices of any path between $x$ and $y$ form a
dominating set), we present an efficient algorithm that finds a minimum
isometric dominating set of such a graph. On the other hand, we prove that even
if one restricts to weak dominating pair graphs that are also chordal graphs,
the problem of deciding whether there exists a convex dominating set bounded by
a given arbitrary positive integer is NP-complete. By further restricting the
class of graphs to chordal dominating pair graphs (i.e.,~the chordal graphs in
which every connected induced subgraph has a dominating pair) we are able to
find a polynomial time algorithm that determines the minimum size of a convex
dominating set of such a graph.