Combinatorics
An upper bound on the 2-outer-independent domination number of a tree
Comptes Rendus. Mathématique, Volume 349 (2011) no. 21-22, pp. 1123-1125.

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 $γ2oi(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 $γ2oi(T)⩽(n+l)/2$, and we characterize the trees attaining this upper bound.

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 $γ2oi(G)$, est le cardinal minimum dʼun ensemble 2-dominant extérieurement-indépendant de G. Nous prouvons lʼinégalité $γ2oi(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.

Accepted:
Published online:
DOI: 10.1016/j.crma.2011.10.005

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_21-22_1123_0,
author = {Marcin Krzywkowski},
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},
}
TY  - JOUR
AU  - Marcin Krzywkowski
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
DO  - 10.1016/j.crma.2011.10.005
LA  - en
ID  - CRMATH_2011__349_21-22_1123_0
ER  - 
%0 Journal Article
%A Marcin Krzywkowski
%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
%R 10.1016/j.crma.2011.10.005
%G en
%F CRMATH_2011__349_21-22_1123_0
Marcin Krzywkowski. An upper bound on the 2-outer-independent domination number of a tree. Comptes Rendus. Mathématique, Volume 349 (2011) no. 21-22, pp. 1123-1125. doi : 10.1016/j.crma.2011.10.005. https://comptes-rendus.academie-sciences.fr/mathematique/articles/10.1016/j.crma.2011.10.005/

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

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

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

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

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

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

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

[8] Y. Jiao; H. Yu 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] R. Shaheen Bounds for the 2-domination number of toroidal grid graphs, International Journal of Computer Mathematics, Volume 86 (2009), pp. 584-588

Cited by Sources: