Global outer connected domination number of a graph
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...
Gespeichert in:
| Datum: | 2018 |
|---|---|
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | English |
| Veröffentlicht: |
Lugansk National Taras Shevchenko University
2018
|
| Schlagworte: | |
| Online Zugang: | https://admjournal.luguniv.edu.ua/index.php/adm/article/view/126 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Algebra and Discrete Mathematics |
Institution
Algebra and Discrete Mathematics| Zusammenfassung: | 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. |
|---|