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

Krzywkowski, Marcin

doi:10.1016/j.crma.2011.10.005

Combinatorics

An upper bound on the 2-outer-independent domination number of a tree
[Borne supérieure sur le nombre de 2-domination extérieurement-indépendante dʼun arbre]

Présenté par : the Editorial Board

Krzywkowski, Marcin ¹

¹ Faculty of Electronics, Telecommunications and Informatics, Gdańsk University of Technology, Narutowicza 11/12, 80–233 Gdańsk, Poland

Comptes Rendus. Mathématique, Tome 349 (2011) no. 21-22, pp. 1123-1125.

Résumé
Abstract

Un ensemble 2-dominant extérieurement-indépendant dʼun graphe G est un ensemble D de sommets de G tel que chaque sommet de $V (G) ∖ D$ a au moins deux voisins dans D, et lʼensemble $V (G) ∖ D$ est indépendant. Le nombre de 2-domination extérieurement-indépendante dʼun graphe G, noté par $γ_{2}^{oi} (G)$ , est le cardinal minimum dʼun ensemble 2-dominant extérieurement-indépendant de G. Nous prouvons lʼinégalité $γ_{2}^{oi} (T) ⩽ (n + l) / 2$ pour tout arbre non trivial T dʼordre n avec l feuilles, et nous caractérisons les arbres atteignant cette borne supérieure.

A 2-outer-independent dominating set of a graph G is a set D of vertices of G such that every vertex of $V (G) ∖ D$ has at least two neighbors in D, and the set $V (G) ∖ D$ is independent. The 2-outer-independent domination number of a graph G, denoted by $γ_{2}^{oi} (G)$ , is the minimum cardinality of a 2-outer-independent dominating set of G. We prove that for every nontrivial tree T of order n with l leaves we have $γ_{2}^{oi} (T) ⩽ (n + l) / 2$ , and we characterize the trees attaining this upper bound.

Reçu le : 2010-12-09
Accepté le : 2011-10-03
Publié le : 2011-10-24

DOI : 10.1016/j.crma.2011.10.005

Affiliations des auteurs :

Krzywkowski, Marcin ¹

¹ Faculty of Electronics, Telecommunications and Informatics, Gdańsk University of Technology, Narutowicza 11/12, 80–233 Gdańsk, Poland

@article{CRMATH_2011__349_21-22_1123_0,
     author = {Krzywkowski, Marcin},
     title = {An upper bound on the 2-outer-independent domination number of a tree},
     journal = {Comptes Rendus. Math\'ematique},
     pages = {1123--1125},
     publisher = {Elsevier},
     volume = {349},
     number = {21-22},
     year = {2011},
     doi = {10.1016/j.crma.2011.10.005},
     language = {en},
     url = {http://www.numdam.org/articles/10.1016/j.crma.2011.10.005/}
}

TY  - JOUR
AU  - Krzywkowski, Marcin
TI  - An upper bound on the 2-outer-independent domination number of a tree
JO  - Comptes Rendus. Mathématique
PY  - 2011
SP  - 1123
EP  - 1125
VL  - 349
IS  - 21-22
PB  - Elsevier
UR  - http://www.numdam.org/articles/10.1016/j.crma.2011.10.005/
DO  - 10.1016/j.crma.2011.10.005
LA  - en
ID  - CRMATH_2011__349_21-22_1123_0
ER  -

%0 Journal Article
%A Krzywkowski, Marcin
%T An upper bound on the 2-outer-independent domination number of a tree
%J Comptes Rendus. Mathématique
%D 2011
%P 1123-1125
%V 349
%N 21-22
%I Elsevier
%U http://www.numdam.org/articles/10.1016/j.crma.2011.10.005/
%R 10.1016/j.crma.2011.10.005
%G en
%F CRMATH_2011__349_21-22_1123_0

Krzywkowski, Marcin. An upper bound on the 2-outer-independent domination number of a tree. Comptes Rendus. Mathématique, Tome 349 (2011) no. 21-22, pp. 1123-1125. doi : 10.1016/j.crma.2011.10.005. http://www.numdam.org/articles/10.1016/j.crma.2011.10.005/

Bibliographie
Cité par

[1] Blidia, M.; Chellali, M.; Favaron, O. Independence and 2-domination in trees, Australasian Journal of Combinatorics, Volume 33 (2005), pp. 317-327

[2] Blidia, M.; Favaron, O.; Lounes, R. Locating-domination, 2-domination and independence in trees, Australasian Journal of Combinatorics, Volume 42 (2008), pp. 309-316

[3] Fink, J.; Jacobson, M. n-Domination in graphs, Graph Theory with Applications to Algorithms and Computer Science, Wiley, New York, 1985, pp. 282-300

[4] Fujisawa, J.; Hansberg, A.; Kubo, T.; Saito, A.; Sugita, M.; Volkmann, L. Independence and 2-domination in bipartite graphs, Australasian Journal of Combinatorics, Volume 40 (2008), pp. 265-268

[5] Hansberg, A.; Volkmann, L. On graphs with equal domination and 2-domination numbers, Discrete Mathematics, Volume 308 (2008), pp. 2277-2281

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

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

[8] Jiao, Y.; Yu, H. On graphs with equal 2-domination and connected 2-domination numbers, Mathematica Applicata Yingyong Shuxue, Volume 17 (2004) no. suppl., pp. 88-92

[9] M. Krzywkowski, 2-outer-independent domination in graphs, submitted for publication.

[10] Shaheen, R. Bounds for the 2-domination number of toroidal grid graphs, International Journal of Computer Mathematics, Volume 86 (2009), pp. 584-588

Cité par Sources :