Title: On Roman domination of circular-arc graphs

Authors: Akul Rana; Angshu Kumar Sinha; Anita Pal

Addresses: Department of Mathematics, Narajole Raj College, Narajole, Paschim Medinipur – 721211, India ' Department of Mathematics, NSHM Knowledge Campus, Durgapur – 713212, India ' Department of Mathematics, National Institute of Technology Durgapur, Durgapur – 713209, India

Abstract: Let G = (V, E) be a graph with vertex set V and edge set E. A Roman dominating function is a mapping f : V → {0, 1, 2} such that every vertex u for which f(u) = 0 is adjacent to at least one vertex v with f(v) = 2. The weight of a Roman dominating function is the value f(V) = Σ_v∈V f(v). The minimum weight of a Roman dominating function on a graph G is called the Roman domination number γ_R(G). The Roman domination problem on a graph G is to find γ_R(G). This problem is NP-complete for general graphs. In this paper, the same problem restricted to a class of graphs called circular-arc graphs are considered. In particular, an O(n²) time algorithm is designed using a dynamic programming approach to compute the Roman domination number of circular arc graphs, one of the non-tree type graph classes. Also, we have obtained the bounds of γ_R(G) for circular-arc graphs.

Keywords: design of algorithms; analysis of algorithms; circular-arc graph; domination; Roman domination.

DOI: 10.1504/IJAIP.2024.140086

International Journal of Advanced Intelligence Paradigms, 2024 Vol.28 No.3/4, pp.209 - 220

Received: 13 Dec 2017
Accepted: 24 Oct 2018
Published online: 24 Jul 2024 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article