article · Springer Link (Chiba Institute of Technology) · 2024

On maximal Roman domination in graphs: complexity and algorithms

Zehui Shao, Yonghao Song, Qiyun Liu, Zhixing Duan, Huiqin Jiang

Cited by 0Abstract and details only

Abstract

For a simple undirected connected graph G = (V, E), a maximal Roman dominating function (MRDF) of G is a function f : V (G) → {0, 1, 2} with the following properties: (i) For every vertex v ∈ {v ∈ V|f(v) = 0}, there exists a vertex u ∈ N(v) such that f(u) = 2. (ii) The set {v ∈ V|f(v) = 0} is not a dominating set of G; In other words, there exists a vertex v ∈ {v ∈ V|f(v) ≠ 0} such that N(v) ∩ {u ∈ V|f(u) = 0} ∅. The weight of an MRDF of G is the sum of its function values over all vertices, denoted as f(G) = ∑v∈V (G) f(v), and the maximal Roman domination number of G, denoted by γmR(G), is the minimum weight of an MRDF of G. In this paper, we establish some bounds of the maximal Roman domination number of graphs. Additionally, we develop an integer linear programming formulation to compute the maximal Roman domination number of any graph. Furthermore, we prove that maximal Roman domination problem (MRD) is NP-complete even restricted to star convex bipartite graphs and chordal bipartite graphs. Lastly, we show the maximal Roman domination number of threshold graphs, trees, and block graphs can be computed in linear time.

Cite this paper

APA 7

Shao, Z., Song, Y., Liu, Q., Duan, Z., & Jiang, H. (2024). On maximal Roman domination in graphs: complexity and algorithms. Springer Link (Chiba Institute of Technology). https://doi.org/10.1051/ro/2024038/pdf

MLA 9

Shao, Zehui, et al. “On maximal Roman domination in graphs: complexity and algorithms.” Springer Link (Chiba Institute of Technology), 2024, https://doi.org/10.1051/ro/2024038/pdf.

Chicago

Shao, Zehui, Yonghao Song, Qiyun Liu, Zhixing Duan, and Huiqin Jiang. 2024. “On maximal Roman domination in graphs: complexity and algorithms.” Springer Link (Chiba Institute of Technology). https://doi.org/10.1051/ro/2024038/pdf.

Harvard

Shao, Z. et al. (2024) ‘On maximal Roman domination in graphs: complexity and algorithms’, Springer Link (Chiba Institute of Technology). Available at: https://doi.org/10.1051/ro/2024038/pdf.

BibTeX

@article{shao2024maximal,
  title = {{On maximal Roman domination in graphs: complexity and algorithms}},
  author = {Shao, Zehui and Song, Yonghao and Liu, Qiyun and Duan, Zhixing and Jiang, Huiqin},
  journal = {Springer Link (Chiba Institute of Technology)},
  year = {2024},
  doi = {10.1051/ro/2024038/pdf}
}

Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.