Roman Domination

Shizhi Wang

S.-T. Yau High School Science Awarded Papers mathscidoc:1608.35034

2009
In his article β€œDefend the Roman Empire!” (1999), Ian Stewart discussed a strategy of Emperor Constantine for defending the Roman Empire. Motivated by this article, Cockayne et al. (2004) introduced the notion of Roman domination in graphs. Let 𝐺 = (𝑉, 𝐸) be a graph. A Roman dominating function of 𝐺 is a function 𝑓 ∢ 𝑉 β†’ {0, 1, 2} such that every vertex 𝑣 for which 𝑓(𝑣) = 0 has a neighbor 𝑒 with 𝑓(𝑒) = 2. The weight of a Roman dominating function 𝑓 is 𝑀(𝑓) =βˆ‘_π‘£βˆˆπ‘‰ 𝑓(𝑣). The Roman domination number of a graph 𝐺, denoted by 𝛾_𝑅(𝐺), is the minimum weight of all possible Roman dominating functions. This paper introduces a quantity 𝑅(π‘₯𝑦) for each pair of non-adjacent vertices {π‘₯, 𝑦 }in 𝐺, called the Roman dominating index of{ π‘₯, 𝑦} , which is defined by &𝑅(π‘₯𝑦) = 𝛾_𝑅(𝐺) βˆ’ 𝛾_𝑅(𝐺 + π‘₯𝑦)&. We prove that 0 ≀ 𝑅(π‘₯𝑦) ≀ 1 and give a necessary and sufficient condition on {π‘₯, 𝑦} for which 𝑅(π‘₯𝑦)= 1. This paper also introduces the Roman-critical graph. We call 𝐺 = (𝑉, 𝐸) Roman-critical if 𝛾_𝑅(𝐺 βˆ’ 𝑒) > 𝛾_𝑅(𝐺) , βˆ€π‘’ ∈ 𝐸 . It is proved that a Roman-critical graph can only be a star graph whose order is not equal to 2, or the union of such graphs. In addition, this paper shows that for each connected graph 𝐺 of order& 𝑛 β‰₯ 3,2 ≀ 𝛾_𝑅(𝐺) ≀frac{4𝑛}{5}&. A family of graphs for which the respective equality holds is also provided. Finally, this paper finds the lower bound of the Roman domination number for 3-regular graphs and the exact value of the Roman domination number for &𝐢_frac{𝑛}{2}*𝑃2& and 3-regular circulant graphs.
No keywords uploaded!
[ Download ] [ 2016-08-13 21:51:55 uploaded by yauawardadmin ] [ 1333 downloads ] [ 0 comments ] [ Cited by 12 ]
@inproceedings{shizhi2009roman,
  title={Roman Domination},
  author={Shizhi Wang},
  url={http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20160813215155434497082},
  year={2009},
}
Shizhi Wang. Roman Domination. 2009. http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20160813215155434497082.
Please log in for comment!
 
 
Contact us: office-iccm@tsinghua.edu.cn | Copyright Reserved