Bounds on the vertex–edge domination number of a tree

Krishnakumari, Balakrishna; Venkatakrishnan, Yanamandram B.; Krzywkowski, Marcin

doi:10.1016/j.crma.2014.03.017

Combinatorics

Bounds on the vertex–edge domination number of a tree
[Bornes sur le nombre de domination sommet–arête d'un arbre]

Présenté par : the Editorial Board

Krishnakumari, Balakrishna ¹ ; Venkatakrishnan, Yanamandram B.¹ ; Krzywkowski, Marcin ^2,³

¹ Department of Mathematics, SASTRA University, Tanjore, Tamil Nadu, India
² Department of Mathematics, University of Johannesburg, South Africa
³ Faculty of Electronics, Telecommunications and Informatics, Gdansk University of Technology, Poland

Comptes Rendus. Mathématique, Tome 352 (2014) no. 5, pp. 363-366.

Résumé
Abstract

Un ensemble sommet–arête dominant d'un graphe G est un ensemble D de sommets de G tel que chaque arête de G soit incidente à un sommet de D ou à un sommet adjacent à un sommet de D. Le nombre de domination sommet–arête d'un graphe G, noté $γ_{ve} (T)$ , est le cardinal minimum d'un ensemble sommet–arête dominant de G. Nous prouvons que, pour chaque arbre T d'ordre $n ⩾ 3$ avec l feuilles et des sommets s de soutien, que nous avons $(n - l - s + 3) / 4 ⩽ γ_{ve} (T) ⩽ n / 3$ , et nous caractérisons les arbres atteignant chacune des limites.

A vertex–edge dominating set of a graph G is a set D of vertices of G such that every edge of G is incident with a vertex of D or a vertex adjacent to a vertex of D. The vertex–edge domination number of a graph G, denoted by $γ_{ve} (T)$ , is the minimum cardinality of a vertex–edge dominating set of G. We prove that for every tree T of order $n ⩾ 3$ with l leaves and s support vertices, we have $(n - l - s + 3) / 4 ⩽ γ_{ve} (T) ⩽ n / 3$ , and we characterize the trees attaining each of the bounds.

Reçu le : 2013-11-22
Accepté le : 2014-03-18
Publié le : 2014-04-03

DOI : 10.1016/j.crma.2014.03.017

Affiliations des auteurs :

Krishnakumari, Balakrishna ¹ ; Venkatakrishnan, Yanamandram B. ¹ ; Krzywkowski, Marcin ^{2, 3}

@article{CRMATH_2014__352_5_363_0,
     author = {Krishnakumari, Balakrishna and Venkatakrishnan, Yanamandram B. and Krzywkowski, Marcin},
     title = {Bounds on the vertex{\textendash}edge domination number of a tree},
     journal = {Comptes Rendus. Math\'ematique},
     pages = {363--366},
     publisher = {Elsevier},
     volume = {352},
     number = {5},
     year = {2014},
     doi = {10.1016/j.crma.2014.03.017},
     language = {en},
     url = {http://www.numdam.org/articles/10.1016/j.crma.2014.03.017/}
}

TY  - JOUR
AU  - Krishnakumari, Balakrishna
AU  - Venkatakrishnan, Yanamandram B.
AU  - Krzywkowski, Marcin
TI  - Bounds on the vertex–edge domination number of a tree
JO  - Comptes Rendus. Mathématique
PY  - 2014
SP  - 363
EP  - 366
VL  - 352
IS  - 5
PB  - Elsevier
UR  - http://www.numdam.org/articles/10.1016/j.crma.2014.03.017/
DO  - 10.1016/j.crma.2014.03.017
LA  - en
ID  - CRMATH_2014__352_5_363_0
ER  -

%0 Journal Article
%A Krishnakumari, Balakrishna
%A Venkatakrishnan, Yanamandram B.
%A Krzywkowski, Marcin
%T Bounds on the vertex–edge domination number of a tree
%J Comptes Rendus. Mathématique
%D 2014
%P 363-366
%V 352
%N 5
%I Elsevier
%U http://www.numdam.org/articles/10.1016/j.crma.2014.03.017/
%R 10.1016/j.crma.2014.03.017
%G en
%F CRMATH_2014__352_5_363_0

Krishnakumari, Balakrishna; Venkatakrishnan, Yanamandram B.; Krzywkowski, Marcin. Bounds on the vertex–edge domination number of a tree. Comptes Rendus. Mathématique, Tome 352 (2014) no. 5, pp. 363-366. doi : 10.1016/j.crma.2014.03.017. http://www.numdam.org/articles/10.1016/j.crma.2014.03.017/

Bibliographie
Cité par

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

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

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

[4] Krzywkowski, M. A lower bound on the total outer-independent domination number of a tree, C. R. Acad. Sci. Paris, Ser. I, Volume 349 (2011), pp. 7-9

[5] Lemańska, M. Lower bound on the domination number of a tree, Discuss. Math., Graph Theory, Volume 24 (2004), pp. 165-169

[6] Lewis, J.; Hedetniemi, S.; Haynes, T.; Fricke, G. Vertex–edge domination, Util. Math., Volume 81 (2010), pp. 193-213

[7] Peters, J. Theoretical and algorithmic results on domination and connectivity, Clemson University, 1986 (PhD thesis)

Cité par Sources :