Comptes Rendus
no. 1-2
Combinatorics
A lower bound on the total outer-independent domination number of a tree
[Une borne inférieure pour le cardinal des sous-ensembles totalement dominants et extérieurement-indépendants d'un arbre]

Présenté par : the Editorial Board

Marcin Krzywkowski1
1 Faculty of Electronics, Telecommunications and Informatics, Gdańsk University of Technology, Narutowicza 11/12, 80-233 Gdańsk, Poland
Comptes Rendus. Mathématique, Volume 349 (2011) no. 1-2, pp. 7-9.

Un sous-ensemble totalement dominant et extérieurement indépendant d'un graphe est un sous-ensemble D des sommets de G tel que chaque sommet de G ait un voisin dans D et l'ensemble V(G)∖D soit indépendant. Le plus petit cardinal d'un tel sous-ensemble est noté γtoi(G). Nous démontrons que pour tout arbre T non trivial, d'ordre n avec l feuilles, nous avons γtoi(T)⩾(2n−2l+2)/3. De plus, nous caractérisons les arbres réalisant cette borne inférieure.

A total outer-independent dominating set of a graph G is a set D of vertices of G such that every vertex of G has a neighbour in D, and the set V(G)∖D is independent. The total outer-independent domination number of a graph G, denoted by γtoi(G), is the minimum cardinality of the total outer-independent dominating set of G. We prove that for every nontrivial tree T of order n with l leaves we have γtoi(T)⩾(2n−2l+2)/3, and we characterize the trees attaining this lower bound.

Reçu le :
Accepté le :
Publié le :
DOI : 10.1016/j.crma.2010.11.021
Marcin Krzywkowski 1

1 Faculty of Electronics, Telecommunications and Informatics, Gdańsk University of Technology, Narutowicza 11/12, 80-233 Gdańsk, Poland 
@article{CRMATH_2011__349_1-2_7_0,
     author = {Marcin Krzywkowski},
     title = {A lower bound on the total outer-independent domination number of a tree},
     journal = {Comptes Rendus. Math\'ematique},
     pages = {7--9},
     publisher = {Elsevier},
     volume = {349},
     number = {1-2},
     year = {2011},
     doi = {10.1016/j.crma.2010.11.021},
     language = {en},
}
TY  - JOUR
AU  - Marcin Krzywkowski
TI  - A lower bound on the total outer-independent domination number of a tree
JO  - Comptes Rendus. Mathématique
PY  - 2011
SP  - 7
EP  - 9
VL  - 349
IS  - 1-2
PB  - Elsevier
DO  - 10.1016/j.crma.2010.11.021
LA  - en
ID  - CRMATH_2011__349_1-2_7_0
ER  - 
%0 Journal Article
%A Marcin Krzywkowski
%T A lower bound on the total outer-independent domination number of a tree
%J Comptes Rendus. Mathématique
%D 2011
%P 7-9
%V 349
%N 1-2
%I Elsevier
%R 10.1016/j.crma.2010.11.021
%G en
%F CRMATH_2011__349_1-2_7_0
Marcin Krzywkowski. A lower bound on the total outer-independent domination number of a tree. Comptes Rendus. Mathématique, Volume 349 (2011) no. 1-2, pp. 7-9. doi : 10.1016/j.crma.2010.11.021. https://comptes-rendus.academie-sciences.fr/mathematique/articles/10.1016/j.crma.2010.11.021/

[1] M. Chellali; T. Haynes A note on the total domination number of a tree, J. Combin. Math. Combin. Comput., Volume 58 (2006), pp. 189-193

[2] E. Cockayne; R. Dawes; S. Hedetniemi Total domination in graphs, Networks, Volume 10 (1980), pp. 211-219

[3] T. Haynes; S. Hedetniemi; P. Slater Fundamentals of Domination in Graphs, Marcel Dekker, New York, 1998

[4] Domination in Graphs: Advanced Topics (T. Haynes; S. Hedetniemi; P. Slater, eds.), Marcel Dekker, New York, 1998

[5] M. Krzywkowski, Total outer-independent domination in graphs, submitted for publication.

Cité par Sources :

Commentaires - Politique

Ces articles pourraient vous intéresser

An upper bound on the 2-outer-independent domination number of a tree

Marcin Krzywkowski

C. R. Math (2011)

Bounds on the vertex–edge domination number of a tree

Balakrishna Krishnakumari; Yanamandram B. Venkatakrishnan; Marcin Krzywkowski

C. R. Math (2014)

Some notes on domination edge critical graphs

Nader Jafari Rad; Sayyed Heidar Jafari

C. R. Math (2011)