Эта публикация цитируется в
1 статье
RESEARCH ARTICLE
Global outer connected domination number of a graph
Morteza Alishahia,
Doost Ali Mojdehb a Department of Mathematics, University of Tafresh, Tafresh, Iran
b Department of Mathematics, University of Mazandaran, Babolsar, Iran
Аннотация:
For a given graph
$G=(V,E)$, a dominating set
$D \subseteq V(G)$ is said to be an outer connected dominating set if
$D=V(G)$ or
$G-D$ is connected. The outer connected domination number of a graph
$G$, denoted by
$\widetilde{\gamma}_c(G)$, is the cardinality of a minimum outer connected dominating set of
$G$. A set
$S \subseteq V(G)$ is said to be a global outer connected dominating set of a graph
$G$ if
$S$ is an outer connected dominating set of
$G$ and
$\overline G$. The global outer connected domination number of a graph
$G$, denoted by
$\widetilde{\gamma}_{gc}(G)$, is the cardinality of a minimum global outer connected dominating set of
$G$. In this paper we obtain some bounds for outer connected domination numbers and global outer connected domination numbers of graphs. In particular, we show that for connected graph
$G\ne K_1$, $ \max\{{n-\frac{m+1}{2}}, \frac{5n+2m-n^2-2}{4}\} \leq \widetilde{\gamma}_{gc}(G) \leq \min\{m(G),m(\overline G)\}$. Finally, under the conditions, we show the equality of global outer connected domination numbers and outer connected domination numbers for family of trees.
Ключевые слова:
global domination, outer connected domination, global outer connected domination, trees.
MSC: 05C69 Поступила в редакцию: 11.12.2015
Язык публикации: английский