Bounds on the vertex-edge domination number of a tree

被引：37

作者：

Krishnakumari, Balakrishna ^{[1
]}

Venkatakrishnan, Yanamandram B. ^{[1
]}

Krzywkowski, Marcin ^{[2
,3
]}

机构：

[1] SASTRA Univ, Dept Math, Tanjore, Tamil Nadu, India

[2] Univ Johannesburg, Dept Math, Johannesburg, South Africa

[3] Gdansk Univ Technol, Fac Elect Telecommun & Informat, Gdansk, Poland

来源：

COMPTES RENDUS MATHEMATIQUE | 2014年 / 352卷 / 05期

关键词：

D O I：

10.1016/j.crma.2014.03.017

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

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 gamma(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 <= gamma(ve)(T) <= n/3, and we characterize the trees attaining each of the bounds. (C) 2014 Academie des sciences. Published by Elsevier Masson SAS. All rights reserved.

引用

页码：363 / 366

页数：4

共 7 条

[1] Chellali M., 2006, Journal of Combinatorial Mathematics and Combinatorial Computing, V58, P189
[2] Haynes T.W., 1998, Chapman & Hall/CRC Pure and Applied Mathematics
[3] Haynes TW, 1998, Fundamentals of domination in graphs, V1st, DOI [DOI 10.1201/9781482246582, 10.1201/9781482246582]
[4] A lower bound on the total outer-independent domination number of a tree
Krzywkowski, Marcin
[J]. COMPTES RENDUS MATHEMATIQUE, 2011, 349 (1-2) : 7 - 9
[5] Lemanska M., 2004, Discussiones Mathematicae Graph Theory, V24, P165, DOI 10.7151/dmgt.1222
[6] Lewis J, 2010, UTILITAS MATHEMATICA, V81, P193
[7] Peters J. W., 1986, THESIS CLEMSON U

← 1 →