Orientable Open Domination of Graphs

Abstract

An open dominating set for a digraph $D$ is a subset $S$ of vertices of $D$ such that every vertex of $D$ is adjacent from some vertex of $S$. The cardinality of a minimum open dominating set for $D$ is the open domination number ${\rho }_1(D)$ of $D$. The lower orientable open domination number ${\text{dom}}_1(G)$ of a graph $G$ is the minimum open domination number among all orientations of $G$. Similarly, the upper orientable open domination number ${\text{DOM}}_1(G)$ of $G$ is the maximum such open
domination number. For a connected graph $G$, it is shown that ${\text{dom}}_1(G)$ and ${\text{DOM}}_1(G)$ exist if and only if $G$ is not a tree. A discussion of the upper orientable open domination number of complete graphs is given. It is shown that for each integer $c$ with ${\text{dom}}_1(K_n)\le c\le {\text{DOM}}_1(K_n)$, there exists an
orientation $D$ of $K_n$ such that ${\rho }_1(D)=c$.