Convex Dominating-Geodetic Partitions in Graphs

Abstract

The distance $d(u,v)$ between two vertices $u$ and $v$ in a connected graph $G$ is the length of a shortest $u-v$ path in $G.$ A $u-v$ path of length $d(u,v)$ is called $u-v$ geodesic. A subset $D$ of $V(G)$ is a dominating set in $G$ if every vertex of $V(G)-D$ has at
least one neighbor in $D.$ A set $X$ is convex in $G$ if  vertices from all $a-b$ geodesics belong to $X$ for every two vertices $a,b\in X.$ A set $X\subseteq V$ is a convex dominating set if $X$ is convex and dominating. The convex domination number $\gamma_{con}(G)$ of a graph $G$ equals the minimum cardinality of a convex dominating set in $G$. A set of vertices $S$ of a graph $G$ is a geodetic set of $G$ if every vertex $v\not\in S$ lies on a $x-y$ geodesic between two vertices $x,y$ of $S$. The minimum cardinality of a geodetic set of $G$ is the geodetic number of $G$ and it is denoted by $g(G)$. A $DS$-pair of a graph $G$ is a pair $(D, S)$ of disjoint nonempty sets of vertices of $G$ such that $D$ is a convex dominating set and $S$ is a geodetic set of $G$. A $DS$-pair $(D, S)$ of $G$ is a convex dominating-geodetic partition of $G$ if $|D| + |S|=|V (G)|$. Moreover, a convex dominating-geodetic partition of $G$ is called exhaustive if $D$ is a $\gamma_{con}(G)$-set and $S$ is a $g(G)$-set. Thus, if $G$ has an exhaustive convex dominating-geodetic partition, then $\gamma_{con}(G)+g(G)=n(G)$. In the present article we study the (exhaustive) convex dominating-geodetic partitions of graph.