Comptes Rendus
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.

Received:
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:

Comments - Policy


Articles of potential interest

A lower bound on the total 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)