Algorithmic aspects of Roman domination in graphs
- PDF / 497,102 Bytes
- 14 Pages / 439.37 x 666.142 pts Page_size
- 8 Downloads / 192 Views
Algorithmic aspects of Roman domination in graphs Chakradhar Padamutham1 · Venkata Subba Reddy Palagiri1 Received: 4 February 2020 © Korean Society for Informatics and Computational Applied Mathematics 2020
Abstract For a simple, undirected graph G = (V , E), a Roman dominating function (RDF) f :V → {0, 1, 2} has the property that, every vertex u with f (u) = 0 is adjacent to at leastone vertex v for which f (v) = 2. The weight of a RDF is the sum f (V ) = v∈V f (v). The minimum weight of a RDF is called the Roman domination number and is denoted by γ R (G). Given a graph G and a positive integer k, the Roman domination problem (RDP) is to check whether G has a RDF of weight at most k. The RDP is known to be NP-complete for bipartite graphs. We strengthen this result by showing that this problem remains NP-complete for two subclasses of bipartite graphs namely, star convex bipartite graphs and comb convex bipartite graphs. We show that γ R (G) is linear time solvable for bounded tree-width graphs, chain graphs and threshold graphs, a subclass of split graphs. The minimum Roman domination problem (MRDP) is to find a RDF of minimum weight in the input graph. We show that the MRDP for star convex bipartite graphs and comb convex bipartite graphs cannot be approximated within (1 − ) ln |V | for any > 0 unless N P ⊆ DT I M E(|V | O(log log |V |) ) and also propose a 2(1 + ln(Δ + 1))-approximation algorithm for the MRDP, where Δ is the maximum degree of G. Finally, we show that the MRDP is APX-complete for graphs with maximum degree 5. Keywords Roman domination · Tree convex bipartite graph · NP-complete · APX-complete Mathematics Subject Classification 05C69 · 68Q25
B
Chakradhar Padamutham [email protected] Venkata Subba Reddy Palagiri [email protected]
1
Department of Computer Science and Engineering, National Institute of Technology, Warangal, Telangana 506 004, India
123
P. Chakradhar, P. V. S. Reddy
1 Introduction Consider G = (V , E) be a simple, undirected and connected graph. For a vertex v ∈ V , the open neighborhood of v in G is N G (v) = {u ∈ V | (u, v) ∈ E} and the closed neighborhood of v is defined as N G [v] = N G (v) ∪ {v}. The degree of a vertex v is |N G (v)| and is denoted by deg(v). The maximum degree of a graph G, denoted by Δ and the minimum degree of a graph, denoted by δ are the maximum and the minimum degree of its vertices. An induced subgraph is a graph formed from a subset D of vertices of G and all of the edges in G connecting pairs of vertices in that subset, denoted by D. A clique is a subset of vertices of G such that every two distinct vertices in the subset are adjacent. An independent set is a set of vertices in which no two vertices are adjacent. A vertex v of G is said to be a pendant vertex if deg(v) = 1 and is called isolated vertex if deg(v) = 0. An edge of G is said to be a pendant edge if one of its vertices is a pendant vertex. A star is a tree on n vertices with one vertex having degree n − 1, called central vertex, and the other n − 1 vertices having degree 1.
Data Loading...
