For a graph G=(V,E) with V=V(G) and E=E(G), a Roman {3}-dominating function is a function f:V→{0,1,2,3} having the property that ∑u∈NG(v)f(u)≥3, if f(v)=0, and ∑u∈NG(v)f(u)≥2, if f(v)=1 for any ...vertex v∈G. The weight of a Roman {3}-dominating function f is the sum f(V)=∑v∈V(G)f(v) and the minimum weight of a Roman {3}-dominating function on G is the Roman {3}-domination number of G, denoted by γ{R3}(G). We initiate the study of Roman {3}-domination and show its relationship to domination, Roman domination, Roman {2}-domination (Italian domination) and double Roman domination. Finally, we present an upper bound on the Roman {3}-domination number of a connected graph G in terms of the order of G and characterize the graphs attaining this bound. Finally, we show that associated decision problem for Roman {3}-domination is NP-complete, even for bipartite graphs.
The variety of domination games Brešar, Boštjan; Bujtás, Csilla; Gologranc, Tanja ...
Aequationes mathematicae,
12/2019, Volume:
93, Issue:
6
Journal Article
Peer reviewed
Open access
Domination game (Brešar et al. in SIAM J Discrete Math 24:979–991,
2010
) and total domination game (Henning et al. in Graphs Comb 31:1453–1462
(2015
) are by now well established games played on ...graphs by two players, named Dominator and Staller. In this paper, Z-domination game, L-domination game, and LL-domination game are introduced as natural companions of the standard domination games. Versions of the Continuation Principle are proved for the new games. It is proved that in each of these games the outcome of the game, which is a corresponding graph invariant, differs by at most one depending whether Dominator or Staller starts the game. The hierarchy of the five domination games is established. The invariants are also bounded with respect to the (total) domination number and to the order of a graph. Values of the three new invariants are determined for paths up to a small constant independent from the length of a path. Several open problems and a conjecture are listed. The latter asserts that the L-domination game number is not greater than 6 / 7 of the order of a graph.
In this paper, we introduce the concept of relatively prime detour domination number for switching graph. If a set S ⊆ V is a detour set, a dominating set with at least two elements, and has (deg(u), ...deg(v)) = 1 for each pair of vertices u and v, then it is said to be a relatively prime detour dominating set of a graph G. The relatively prime detour domination number of a graph G is known as γrpdn(G) and represents the lowest cardinality of a relatively prime detour dominating set. First, we explain the concept of a switching graph before producing some conclusions based on the switching graphs of helm, fan, complete, spider, and sunlet graphs that have relatively prime detour domination numbers.
Total Roman {3}-domination in Graphs Shao, Zehui; Mojdeh, Doost Ali; Volkmann, Lutz
Symmetry (Basel),
02/2020, Volume:
12, Issue:
2
Journal Article
Peer reviewed
Open access
For a graph G = ( V , E ) with vertex set V = V ( G ) and edge set E = E ( G ) , a Roman { 3 } -dominating function (R { 3 } -DF) is a function f : V ( G ) → { 0 , 1 , 2 , 3 } having the property ...that ∑ u ∈ N G ( v ) f ( u ) ≥ 3 , if f ( v ) = 0 , and ∑ u ∈ N G ( v ) f ( u ) ≥ 2 , if f ( v ) = 1 for any vertex v ∈ V ( G ) . The weight of a Roman { 3 } -dominating function f is the sum f ( V ) = ∑ v ∈ V ( G ) f ( v ) and the minimum weight of a Roman { 3 } -dominating function on G is the Roman { 3 } -domination number of G, denoted by γ { R 3 } ( G ) . Let G be a graph with no isolated vertices. The total Roman { 3 } -dominating function on G is an R { 3 } -DF f on G with the additional property that every vertex v ∈ V with f ( v ) ≠ 0 has a neighbor w with f ( w ) ≠ 0 . The minimum weight of a total Roman { 3 } -dominating function on G, is called the total Roman { 3 } -domination number denoted by γ t { R 3 } ( G ) . We initiate the study of total Roman { 3 } -domination and show its relationship to other domination parameters. We present an upper bound on the total Roman { 3 } -domination number of a connected graph G in terms of the order of G and characterize the graphs attaining this bound. Finally, we investigate the complexity of total Roman { 3 } -domination for bipartite graphs.
Effects on fractional domination in graphs Shanthi, P.; Amutha, S.; Anbazhagan, N. ...
Journal of intelligent & fuzzy systems,
05/2023, Volume:
44, Issue:
5
Journal Article
Peer reviewed
A graph G is an undirected finite connected graph. A function f : V (G) → 0, 1 is called a fractional dominating function if, ∑u∈Nvf (u) ≥1, for all v ∈ V, where N v is the closed neighborhood of v. ...The weight of a fractional dominating function is w (f) = ∑v∈V(G)f (v). The fractional domination number γf (G) has the least weight of all the fractional dominating functions of G. In this paper, we analyze the effects on γf (G) of deleting a vertex from G. Additionally, some bounds on γf (G) are discussed, and provide the exactness of some bounds. If we remove any leaves from any tree T, then the resulting graphs are , where |l| is the number of leaves. Some of the results are proved by the eccentricity value of a vertex e (v).
A Roman dominating function (RDF) on a graph G is a function f:V(G)→{0,1,2} such that every vertex u∈V(G) with f(u)=0 is adjacent to at least one vertex v∈V(G) with f(v)=2. An independent Roman ...dominating function (IRDF) f on a graph G is a Roman dominating function such that the set of vertices u∈V(G) with f(u)∈{1,2} form an independent set on G. The weight of f is f(V(G))=∑v∈V(G)f(v). The minimum weight of an RDF (IRDF) on G is the Roman domination number (independent Roman domination number) of G, denoted by γR(G) (iR(G)). The (independent) Roman domination problem asks for an (independent) Roman dominating function with minimum weight. In this work, we prove that the decision version of the (independent) Roman domination problem is NP-complete even when restricted to planar bipartite graphs with maximum degree three. Moreover, we study the (independent) Roman domination number on three infinite families of snarks. More specifically, we determine the (independent) Roman domination number for generalized Blanuša snarks and we present lower and upper bounds for the (independent) Roman domination number of Goldberg snarks and Loupekine Snarks.
Double Roman domination in trees Zhang, Xiujun; Li, Zepeng; Jiang, Huiqin ...
Information processing letters,
June 2018, 2018-06-00, Volume:
134
Journal Article
Peer reviewed
A subset S of the vertex set of a graph G is a dominating set if every vertex of G not in S has at least one neighbor in S. The domination number γ(G) is defined to be the minimum cardinality among ...all dominating set of G.
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 f is the value f(V(G))=∑u∈V(G)f(u). The minimum weight of a Roman dominating function on a graph G is called the Roman domination numberγR(G) of G.
A double Roman dominating function on a graph G is a function f:V(G)→{0,1,2,3} satisfying the condition that every vertex u for which f(u)=0 is adjacent to at least one vertex v for which f(v)=3 or two vertices v1 and v2 for which f(v1)=f(v2)=2, and every vertex u for which f(u)=1 is adjacent to at least one vertex v for which f(v)≥2. The weight of a double Roman dominating function f is the value f(V(G))=∑u∈V(G)f(u). The minimum weight of a double Roman dominating function on a graph G is called the double Roman domination numberγdR(G) of G. Beeler et al. (2016) 6 showed that 2γ(G)≤γdR(G)≤3γ(G) and showed that 2γ(T)+1≤γdR(T)≤3γ(T) for any non-trivial tree T and posed a problem that if it is possible to construct a polynomial algorithm for computing the value of γdR(T) for any tree T. In this paper, we answer this problem by giving a linear time algorithm to compute the value of γdR(T) for any tree T. Moreover, we give characterizations of trees with 2γ(T)+1=γdR(T) and γdR(T)+1=2γR(T).
•A linear time algorithm to compute the double Roman domination of trees is presented.•A characterization of trees T with γdR(T)=2γ(T)+1 is given.•A characterization of trees T with γdR(T)+1=2γR(T) is given.
PDF
