The convex domination subdivision number of a graph

Abstract

Let $G=(V,E)$ be a simple graph‎. ‎A set $D\subseteq V$ is a‎ ‎dominating set of $G$ if every vertex in $V\setminus D$ has at‎ ‎least one neighbor in $D$‎. ‎The distance $d_G(u,v)$ between two‎ ‎vertices $u$ and $v$ is the length of a shortest $(u,v)$-path in‎ ‎$G$‎. ‎An $(u,v)$-path of length $d_G(u,v)$ is called an‎ ‎$(u,v)$-geodesic‎. ‎A set $X\subseteq V$ is convex in $G$ if‎ ‎vertices from all $(a‎, ‎b)$-geodesics belong to $X$ for any two‎ ‎vertices $a,b\in X$‎. ‎A set $X$ is a convex dominating set if it is‎ ‎convex and dominating set‎. ‎The {\em convex domination number}‎ ‎$\gamma_{\rm con}(G)$ of a graph $G$ equals the minimum‎ ‎cardinality of a convex dominating set in $G$‎. ‎{\em The convex‎ ‎domination subdivision number} sd$_{\gamma_{\rm con}}(G)$ is the‎ ‎minimum number of edges that must be subdivided (each edge in $G$‎ ‎can be subdivided at most once) in order to increase the convex‎ ‎domination number‎. ‎In this paper we initiate the study of convex‎ ‎domination subdivision number and we establish upper bounds for‎ ‎it‎.

Keywords

• convex dominating set‎
• ‎convex domination number‎