Bounds on the hop domination number of a tree

被引：44

作者：

Ayyaswamy, S. K. ^{[1
]}

Krishnakumari, B. ^{[1
]}

Natarajan, C. ^{[1
]}

Venkatakrishnan, Y. B. ^{[1
]}

机构：

[1] SASTRA Univ, Dept Math, Tanjore 613401, India

来源：

PROCEEDINGS OF THE INDIAN ACADEMY OF SCIENCES-MATHEMATICAL SCIENCES | 2015年 / 125卷 / 04期

关键词：

Hop domination; tree;

D O I：

10.1007/s12044-015-0251-6

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

A hop dominating set of a graph G is a set D of vertices of G if for every vertex of V(G) \ D, there exists u is an element of D such that d(u,v) = 2. The hop domination number of a graph G, denoted by gamma(h) (G), is the minimum cardinality of a hop dominating set of G. We prove that for every tree T of order n with l leaves and s support vertices we have (n-l-s+4)/3 <= gamma(h) (G) <= n/2, and characterize the trees attaining each of the bounds.

引用

页码：449 / 455

页数：7

共 6 条

[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 [J].

Krzywkowski, Marcin .

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]

Natarajan C, PREPRINT

← 1 →