A Roman Domination Chain

详细信息    查看全文

• 作者：Mustapha Chellali ; Teresa W. Haynes ; Sandra M. Hedetniemi…
• 关键词：Roman domination ; Roman independence ; Roman irredundance ; Roman parameters
• 刊名：Graphs and Combinatorics
• 出版年：2016
• 出版时间：January 2016
• 年：2016
• 卷：32
• 期：1
• 页码：79-92
• 全文大小：421 KB
• 参考文献：1.Bermudo, S., Fernau, H., Sigarreta, J.M.: The differential and the Roman domination number of a graph. Appl. Anal. Discret. Math. 8, 155–171 (2014)MathSciNet CrossRef
  2.Bollobás, B., Cockayne, E.J.: Graph-theoretic parameters concerning domination, independence, and irredundance. J. Graph Theory 3, 241–249 (1979)MATH MathSciNet CrossRef
  3.Chellali, M., Rad, N.J.: Strong equality between the Roman domination and independent Roman domination numbers in trees. Discuss. Math. Graph Theory 33, 337–346 (2013)MATH MathSciNet CrossRef
  4.Chellali, M., Rad, N.J.: A note on the independent Roman domination in unicyclic graphs. Opusc. Math. 32, 715–718 (2012)MATH CrossRef
  5.Cockayne, E.J., Dreyer Sr, P.M., Hedetniemi, S.M., Hedetniemi, S.T.: On Roman domination in graphs. Discret. Math. 278, 11–22 (2004)MATH MathSciNet CrossRef
  6.Cockayne, E.J., Hedetniemi, S.T., Miller, D.J.: Properties of hereditary hypergraphs and middle graphs. Can. Math. Bull. 21, 461–468 (1978)MATH MathSciNet CrossRef
  7.Hedetniemi, S.T., Rubalcaba, R.R., Slater, P.J., Walsh, M.: Few Compare to the Great Roman Empire. Congr. Numer. 217, 129–136 (2013)MATH MathSciNet
  8.Rad, N.J., Volkmann, L.: Roman domination perfect graphs. An. Ştiinţ. Univ. “Ovidius” Constanţa, Ser. Mat., vol. 19, No. 3, pp. 167–174 (2011)
  9.ReVelle, C.S., Rosing, K.E.: Defendens imperium romanum: a classical problem in military strategy. Am. Math. Mon. 107(7), 585–594 (2000)MATH MathSciNet CrossRef
  10.Stewart, I.: Defend the Roman Empire!. Sci. Am. 281(6), 136–139 (1999)CrossRef
  11.Targhi, M.A.E.E., Rad, N.J., Moradi, M.S.: Properties of independent Roman domination in graphs. Australas. J. Combin. 52, 11–18 (2012)MATH MathSciNet
  12.Targhi, E.E., Rad, N.J., Mynhardt, C.M., Wu, Y.: Bounds for the independent Roman domination number in graphs. J. Combin. Math. Combin. Comput. 80, 351–365 (2012)MATH MathSciNet
  
• 作者单位：Mustapha Chellali (1)
  Teresa W. Haynes (2) (3)
  Sandra M. Hedetniemi (4)
  Stephen T. Hedetniemi (5)
  Alice A. McRae (6)
  
  1. LAMDA-RO Laboratory, Department of Mathematics, University of Blida, B.P. 270, Blida, Algeria
  2. Department of Mathematics, East Tennessee State University, Johnson City, TN, 37614, USA
  3. Department of Mathematics, University of Johannesburg, Auckland Park, South Africa
  4. School of Computing, Clemson University, Clemson, SC, 29634, USA
  5. Professor Emeritus, School of Computing, Clemson University, Clemson, SC, 29634, USA
  6. Computer Science Department, Appalachian State University, Boone, NC, 28608-2133, USA
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Combinatorics
  Engineering Design
  
• 出版者：Springer Japan
• ISSN：1435-5914

文摘

For a graph \(G=(V,E)\), a Roman dominating function \(f:V\rightarrow \{0,1,2\}\) has the property that every vertex \(v\in V\) with \(f(v)=0\) has a neighbor \(u\) with \(f(u)=2\). The weight of a Roman dominating function \(f\) is the sum \(f(V)=\sum \nolimits _{v\in V}f(v)\), and the minimum weight of a Roman dominating function on \(G\) is the Roman domination number of \(G\). In this paper, we define the Roman independence number, the upper Roman domination number and the upper and lower Roman irredundance numbers, and then develop a Roman domination chain parallel to the well-known domination chain. We also develop sharpness, strictness and bounds for the Roman domination chain inequalities. Keywords Roman domination Roman independence Roman irredundance Roman parameters