Roman domination on strongly chordal graphs

Chun Hung Liu, Gerard J. Chang

Research output: Contribution to journalArticlepeer-review

90 Scopus citations


Given real numbers b≥a>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 b≥a>0, and the weighted independent (a,b)-Roman domination problem with 2a≥b≥a>0 on strongly chordal graphs with a strong elimination ordering provided.

Original languageEnglish (US)
Pages (from-to)608-619
Number of pages12
JournalJournal of Combinatorial Optimization
Issue number3
StatePublished - Oct 2013

All Science Journal Classification (ASJC) codes

  • Computer Science Applications
  • Discrete Mathematics and Combinatorics
  • Control and Optimization
  • Computational Theory and Mathematics
  • Applied Mathematics


  • Bipartite graphs
  • Chordal graphs
  • Domination
  • Roman domination
  • Split graphs
  • Strongly chordal graphs


Dive into the research topics of 'Roman domination on strongly chordal graphs'. Together they form a unique fingerprint.

Cite this