Chinese Quarterly Journal of Mathematics ›› 2006, Vol. 21 ›› Issue (3): 358-367.

Previous Articles     Next Articles

Roman Domination Number and Domination Number of a Tree

  

  1. College of Mathematics and Information Science, Henan University, Kaifeng 475001, China; Department of Mathematics, Zhengzhou University, Zhengzhou 450052, China; Department of Basic Course, Pingdingshan Institute of Technology, Pingdingshan 467000, China
  • Received:2005-10-11 Online:2006-09-30 Published:2023-11-28
  • About author:Song Xiao-xin(1973-),male,native of Jiangyan,Jiangsu,Ph.D.,an associate professor of Henan University,engages in graph theory.
  • Supported by:
     Supported by the NSF of education Department of Henan Province(200510475038);

Abstract: A Roman dominating function on a graph G = (V, E) is a function f : V→{0, 1, 2} satisfying the condition that every vertex u for which f(u) = 0 is adjacent to at least one vertex v for which f(v) - 2. The weight of a Roman dominating function is the value . The minimum weight of a Roman dominating function on a graph G, denoted byγR(G), is called the Roman dominating number of G. In this paper, we will characterize a tree T with γR(T) =γ(T) + 3.

Key words: Roman dominating function, Roman dominating number, dominating number, healthy spider, wounded spider

CLC Number: