Roman domination on strongly chordal graphs Academic Article uri icon


  • Given real numbers ba>0, an (a,b)-Roman dominating function of a graph G=(V,E) is a function f:V{0,a,b} such that every vertex v with f(v)=0 has a neighbor u with f(u)=b. An independent/connected/total (a,b)-Roman dominating function is an (a,b)-Roman dominating function f such that {v V:f(v)0} induces a subgraph without edges/that is connected/without isolated vertices. For a weight function w{:} V , the weight of f is w(f)= v V w(v)f(v). The weighted (a,b)-Roman domination number (a,b)R(G,w) is the minimum weight of an (a,b)-Roman dominating function of G. Similarly, we can define the weighted independent (a,b)-Roman domination number (a,b)Ri(G,w). In this paper, we first prove that for any fixed (a,b) the (a,b)-Roman domination and the total/connected/independent (a,b)-Roman domination problems are NP-complete for bipartite graphs. We also show that for any fixed (a,b) the (a,b)-Roman domination and the total/connected/weighted independent (a,b)-Roman domination problems are NP-complete for chordal graphs. We then give linear-time algorithms for the weighted (a,b)-Roman domination problem with ba>0, and the weighted independent (a,b)-Roman domination problem with 2aba>0 on strongly chordal graphs with a strong elimination ordering provided. 2012 Springer Science+Business Media, LLC.

published proceedings

  • Journal of Combinatorial Optimization

author list (cited authors)

  • Liu, C., & Chang, G. J.

citation count

  • 57

complete list of authors

  • Liu, Chun-Hung||Chang, Gerard J

publication date

  • January 2012