TY - JOUR
ID - 13544
TI - The convex domination subdivision number of a graph
JO - Communications in Combinatorics and Optimization
JA - CCO
LA - en
SN - 2538-2128
AU - Dettlaff, M.
AU - Kosari, S.
AU - Lemańska, M.
AU - Sheikholeslami, S.M.
AD - Gdańsk University of Technology
AD - Azarbaijan Shahid Madani University
Y1 - 2016
PY - 2016
VL - 1
IS - 1
SP - 43
EP - 56
KW - convex dominating set
KW - convex domination number
KW - convex domination subdivision number
DO - 10.22049/cco.2016.13544
N2 - 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.
UR - http://comb-opt.azaruniv.ac.ir/article_13544.html
L1 - http://comb-opt.azaruniv.ac.ir/article_13544_b044108d0b0eedf90a89cf1f47c4f8e0.pdf
ER -