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

Marcin Krzywkowski

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

Marcin Krzywkowski ¹

¹ 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. 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 :

Marcin Krzywkowski ¹

¹ 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/

Bibliographie
Cité par

[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

Cité par Sources :

Commentaires - Politique

Ces articles pourraient vous intéresser

A lower bound on the total outer-independent domination number of a tree

Marcin Krzywkowski

C. R. Math (2011)

Some notes on domination edge critical graphs

Nader Jafari Rad; Sayyed Heidar Jafari

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)