A note on Roman domination in graphs

Hua-Ming Xing, Xin Chen and Xue-Gang Chen
Discrete Mathematics
Volume 306, Issue 24 , 28 December 2006, Pages 3338-3340
http://dx.doi.org/10.1016/j.disc.2006.06.018

一部で流行っているRoman dominationに関する研究．
グラフのRoman dominationとは，各頂点への{0,1,2}の値の割当で，0が割り当てられている頂点の希望に2が割り当てられている頂点が必ず存在するようなもののことであり，Roman dominationのコストとは割当値の総和のことである．
コスト最小のRoman dominationを求める問題を考える．
これは上で挙げたbroadcast dominationで，とりうる値を0,1,2に限定したものに似ているが，若干違う．
この論文では，Roman dominationの最小コストとdominating numberの差がkになるようなグラフの特徴付けを全てのkに対して与えている．