|
Algebra and Discrete Mathematics, 2018, Volume 25, Issue 1, Pages 18–26
(Mi adm640)
|
|
|
|
This article is cited in 1 scientific paper (total in 1 paper)
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
Abstract:
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.
Keywords:
global domination, outer connected domination, global outer connected domination, trees.
Received: 11.12.2015
Citation:
Morteza Alishahi, Doost Ali Mojdeh, “Global outer connected domination number of a graph”, Algebra Discrete Math., 25:1 (2018), 18–26
Linking options:
https://www.mathnet.ru/eng/adm640 https://www.mathnet.ru/eng/adm/v25/i1/p18
|
Statistics & downloads: |
Abstract page: | 282 | Full-text PDF : | 98 | References: | 23 |
|