On the Complexity of Reinforcement in Graphs
We show that the decision problem for p-reinforcement, p-total rein- forcement, total restrained reinforcement, and k-rainbow reinforcement are NP-hard for bipartite graphs.
On the defining number for vertex colorings of a family of graphs.
Strong Equality Between the Roman Domination and Independent Roman Domination Numbers in Trees
A Roman dominating function (RDF) on a graph G = (V,E) is a function f : V −→ {0, 1, 2} satisfying the condition that every vertex u for which f(u) = 0 is adjacent to at least one vertex v for which f(v) = 2. The weight of an RDF is the value f(V (G)) = P u2V (G) f(u). An RDF f in a graph G is independent if no two vertices assigned positive values are adjacent. The Roman domination number R(G) (respectively, the independent Roman domination number iR(G)) is the minimum weight of an RDF (respectively,...
Characterization of Cubic Graphs G with ir t (G) = Ir t (G) = 2
A subset S of vertices in a graph G is called a total irredundant set if, for each vertex v in G, v or one of its neighbors has no neighbor in S −{v}. The total irredundance number, ir(G), is the minimum cardinality of a maximal total irredundant set of G, while the upper total irredundance number, IR(G), is the maximum cardinality of a such set. In this paper we characterize all cubic graphs G with irt(G) = IRt(G) = 2
Roman bondage in graphs
A Roman dominating function on a graph G is a function f:V(G) → 0,1,2 satisfying the condition that every vertex u for which f(u) = 0 is adjacent to at least one vertex v for which f(v) = 2. The weight of a Roman dominating function is the value . The Roman domination number, , of G is the minimum weight of a Roman dominating function on G. In this paper, we define the Roman bondage of a graph G with maximum degree at least two to be the minimum cardinality of all sets E’ ⊆ E(G) for which ....
On The Roman Domination Stable Graphs
A Roman dominating function (or just RDF) on a graph G = (V,E) is a function f : V → {0, 1, 2} satisfying the condition that every vertex u for which f(u) = 0 is adjacent to at least one vertex v for which f(v) = 2. The weight of an RDF f is the value f(V (G)) = Pu2V (G) f(u). The Roman domination number of a graph G, denoted by R(G), is the minimum weight of a Roman dominating function on G. A graph G is Roman domination stable if the Roman domination number of G remains unchanged under removal...
Bounds on the Locating Roman Domination Number in Trees
A Roman dominating function (or just RDF) on a graph G = (V, E) is a function f : V → 0, 1, 2 satisfying the condition that every vertex u for which f(u) = 0 is adjacent to at least one vertex v for which f(v) = 2. The weight of an RDF f is the value f(V (G)) = ∑u∈V(G) f(u). An RDF f can be represented as f = (V0, V1, V2), where Vi = v ∈ V : f(v) = i for i = 0, 1, 2. An RDF f = (V0, V1, V2) is called a locating Roman dominating function (or just LRDF) if N(u) ∩ V2 ≠ N(v) ∩ V2 for any pair u, v of...
A Note on the p−Center Problem
On the intersection graphs of ideals of direct product of rings
In this paper we first calculate the number of vertices and edges of the intersection graph of ideals of direct product of rings and fields. Then we study Eulerianity and Hamiltonicity in the intersection graph of ideals of direct product of commutative rings.
Various Bounds for Liar’s Domination Number
Let G = (V,E) be a graph. A set S ⊆ V is a dominating set if Uv∈S N[v] = V , where N[v] is the closed neighborhood of v. Let L ⊆ V be a dominating set, and let v be a designated vertex in V (an intruder vertex). Each vertex in L ∩ N[v] can report that v is the location of the intruder, but (at most) one x ∈ L ∩ N[v] can report any w ∈ N[x] as the intruder location or x can indicate that there is no intruder in N[x]. A dominating set L is called a liar’s dominating set if every v ∈ V (G) can be correctly...
Page 1