科研之友
微信
新浪微博
Facebook
分享链接
摘要
The Roman domination number and Italian domination number (also known as the Roman {2}-domination number) are graph labeling problems in which each vertex is labeled with either 0, 1, or 2. In the Roman domination problem, each vertex labeled 0 must be adjacent to at least one vertex labeled 2. In the Italian domination problem, each vertex labeled 0 must have the labels of the vertices in its closed neighborhood sum to at least two. The Italian domination number, gamma(1)(G), of a graph G is the minimum possible sum of such a labeling, where the sum is taken over all the vertices in G. It is known that if T is a tree with at least two vertices, then gamma(T) + 1 <= gamma(1)(T) <= 2 gamma (T). In this paper, we characterize the trees T for which gamma(T) + 1 = gamma(1)(T), and we characterize the trees T for which gamma(1)(T) = 2 gamma (T).
- 出版日期2017-1-30
