On the outer-connected domination in graphs

Autor:	Seyed Mahmoud Sheikholeslami, Roslan Hasni, Odile Favaron, Hossein Karami, M. H. Akhbari
Rok vydání:	2011
Předmět:	Combinatorics Discrete mathematics Control and Optimization Computational Theory and Mathematics Domination analysis Dominating set Applied Mathematics Discrete Mathematics and Combinatorics Connected domination Graph Computer Science Applications Mathematics Vertex (geometry)
Zdroj:	Journal of Combinatorial Optimization. 26:10-18
ISSN:	1573-2886 1382-6905
DOI:	10.1007/s10878-011-9427-x
Popis:	A set S of vertices of a graph G is an outer-connected dominating set if every vertex not in S is adjacent to some vertex in S and the subgraph induced by V?S is connected. The outer-connected domination number $\widetilde{\gamma}_{c}(G)$ is the minimum size of such a set. We prove that if ?(G)?2 and diam?(G)?2, then $\widetilde{\gamma}_{c}(G)\le (n+1)/2$ , and we study the behavior of $\widetilde{\gamma}_{c}(G)$ under an edge addition.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::7babd7d91bbd5d8402082aac598a5d57 https://doi.org/10.1007/s10878-011-9427-x Zobrazit plný text záznamu Full text from SpringerLink