The convex domination subdivision number of a graph

Document Type: Original paper

Authors

1 Gdańsk University of Technology

2 Azarbaijan Shahid Madani University

Abstract

Let $G=(V,E)$ be a simple graph. A set $Dsubseteq V$ is a
dominating set of $G$ if every vertex in $Vsetminus 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 $Xsubseteq V$ is convex in $G$ if
vertices from all $(a, b)$-geodesics belong to $X$ for any two
vertices $a,bin 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

Main Subjects