Search

For a simple, undirected, connected graph G , a function h : V (G) → { 0 , 1 , 2 } which satisfies the following conditions is called a weakly connected Roman dominating function (WCRDF) of G with weight h (V) = ∑ p ∈ V h (p). (C1). For all q ∈ V with h (q) = 0 there exists a vertex r such that (q , r) ∈ E and h (r) = 2 and (C2). The graph with vertex set V (G) and edge set { (p , z) : h (p) ≥ 1 or h (z) ≥ 1 or both } is connected. The problem of determining WCRDF of minimum weight is called minimum weakly connected Roman domination problem (MWCRDP). In this paper, we show that MWCRDP is polynomial time solvable for bounded treewidth graphs, threshold graphs and chain graphs. We design a 2 (1 +) (1 + ln (Δ − 1)) -approximation algorithm for the MWCRDP and show that the same cannot have (1 − δ) ln | V | ratio approximation algorithm for any δ > 0 unless P = N P. Next, we show that MWCRDP is APX-hard for graphs with Δ = 4. We also show that the domination and weakly connected Roman domination problems are not equivalent in computational complexity aspects. Finally, two different integer linear programming formulations for MWCRDP are proposed. [ABSTRACT FROM AUTHOR]

A vertex v of a simple graph G = (V,E) ve-dominates every edge incident to v as well as every edge adjacent to these incident edges. A set D ⊆ V is a total vertex-edge dominating set if every edge of E is ve-dominated by a vertex of D and the subgraph induced by D has no isolated vertex. The total vertex-edge domination problem is to find a total vertex-edge dominating set of minimum cardinality. In this paper, we first show that the total vertex-edge domination problem is NP-complete for chordal graphs. Then we provide a linear-time algorithm for this problem in trees. Moreover, we show that the minimum total vertex-edge domination problem cannot be approximated within (1 − 휀)ln |V | for any 휀 > 0 unless NP ⊆DTIME(|V |O(loglog |V |)). Finally, we prove that the minimum total vertex-edge domination problem is APX-complete for bounded-degree graphs. [ABSTRACT FROM AUTHOR]

For a simple, undirected, connected graph G , a function h : V (G) → { 0 , 1 , 2 , 3 } which satisfies the following conditions is called a total Roman {3}-dominating function (TR3DF) of G with weight h (V) = ∑ p ∈ V h (p) : (C1) For every vertex u ∈ V if h (u) = 0 , then u has m (m ≥ 1) neighbors such that whose sum is at least 3, and if h (u) = 1 , then u has n (n ≥ 1) neighbors such that whose sum is at least 2. (C2) The subgraph induced by the set of vertices labeled one, two or three has no isolated vertices. For a graph G , the smallest possible weight of a TR3DF of G denoted γ t { R 3 } (G) is known as the total Roman { 3 } -domination number of G. The problem of determining γ t { R 3 } (G) of a graph G is called minimum total Roman {3}-domination problem (MTR3DP). In this paper, we show that the problem of deciding if G has a TR3DF of weight at most l for chordal graphs is NP-complete. We also show that MTR3DP is polynomial time solvable for bounded treewidth graphs, chain graphs and threshold graphs. We design a 3 (ln (Δ − 0. 5) + 1. 5) -approximation algorithm for the MTR3DP and show that the same cannot have (1 − δ) ln | V | ratio approximation algorithm for any δ > 0 unless NP ⊆ DTIME (| V | O (log log | V |)). Next, we show that MTR3DP is APX-complete for graphs with Δ = 4. We also show that the domination and total Roman {3}-domination problems are not equivalent in computational complexity aspects. Finally, we present an integer linear programming formulation for MTR3DP. [ABSTRACT FROM AUTHOR]

In a graph G = (V , E) , the degree of a vertex v ∈ V , denoted by d G (v) , is defined as the number of edges incident on v. A set D of vertices of G is called a strong dominating set if for every v ∈ V \ D , there exists a vertex u ∈ D such that u v ∈ E and d G (u) ≥ d G (v). For a given graph G , Min-Strong-DS is the problem of finding a strong dominating set of minimum cardinality. The decision version of Min-Strong-DS is shown to be NP -complete for chordal graphs. In this paper, we present polynomial time algorithms for computing a strong dominating set in block graphs and proper interval graphs, two subclasses of chordal graphs. On the other hand, we show that for a graph G with n -vertices, Min-Strong-DS cannot be approximated within a factor of (1 2 − 𝜀) ln n for every 𝜀 > 0 , unless NP ⊆ DTIME ( n O (log log n) ). We also show that Min-Strong-DS is APX -complete for graphs with maximum degree 3. On the positive side, we show that Min-Strong-DS can be approximated within a factor of O (ln Δ) for graphs with maximum degree Δ. [ABSTRACT FROM AUTHOR]