Convex Dominating-Geodetic Partitions in Graphs

Ismael González Yero, Magdalena Lemańska

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 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 of vertices $D$ is dominating in $G$ if every vertex of $V-D$ has at least one neighbor in $D$. 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\notin 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)$. Let $D,S$ be a convex dominating set and a geodetic set in $G$, respectively. The two sets $D$ and $S$ form a convex dominating-geodetic partition of $G$ if $|D|+|S|=|V(G)|$. Moreover, a convex dominating-geodetic partition of $G$ is called optimal if $D$ is a $\gamma_{con}(G)$-set and $S$ is a $g(G)$-set. In the present article we study the (optimal) convex dominating-geodetic partitions of graphs.