Bounds on the hop domination number of a tree

Proceedings Mathematical Sciences

Y B Venkatakrishnan¹  S K Ayyaswamy²  B Krishnakumari¹  C Natarajan¹ 

[1] $$;Department of Mathematics, SASTRA University, Tanjore 0, India$$

关键词: Hop domination;    tree.;   

DOI  :  

学科分类：数学（综合）

来源: Indian Academy of Sciences

【 摘 要 】

A hop dominating set of a graph 𝐺 is a set 𝐷 of vertices of 𝐺 if for every vertex of 𝑉 (𝐺)D, there exists $u in D$ such that 𝑑(𝑢, 𝑣) = 2. The hop domination number of a graph 𝐺, denoted by 𝛾ℎ(𝐺), is the minimum cardinality of a hop dominating set of 𝐺. We prove that for every tree 𝑇 of order 𝑛 with 𝑙 leaves and 𝑠 support vertices we have (𝑛−𝑙−𝑠 +4)/3 ≤ 𝛾ℎ(𝐺) ≤ 𝑛/2, and characterize the trees attaining each of the bounds.

【 授权许可】

Unknown