全部 标题 作者
关键词 摘要

OALib Journal期刊
ISSN: 2333-9721
费用:99美元

查看量下载量

相关文章

更多...

Bounding the domination number of a tree in terms of its annihilation number

Keywords: annihilation number , dominating set , domination number

Full-Text   Cite this paper   Add to My Lib

Abstract:

A set $S$ of vertices in a graph $G$ is a dominating set if every vertex of $V-S$ is adjacent to some vertex in $S$. The domination number $gamma(G)$ is the minimum cardinality of a dominating set in $G$. The annihilation number $a(G)$ is the largest integer $k$ such that the sum of the first $k$ terms of the non-decreasing degree sequence of $G$ is at most the number of edges in $G$. In this paper, we show that for any tree $T$ of order $nge 2$, $gamma(T)le frac{3a(T)+2}{4}$, and we characterize the trees achieving this bound.

Full-Text

comments powered by Disqus

Contact Us

service@oalib.com

QQ:3279437679

WhatsApp +8615387084133