A Roman{3}-dominating function on a graph G is a function f:V(G)→{0,1,2,3} having the property that for any vertex u∈V(G), if f(u)=0, then ∑v∈NG(u)f(v)≥3, and if f(u)=1, then ∑v∈NG(u)f(v)≥2. The ...weight of a Roman {3}-dominating function f is the sum f(V(G))=∑v∈V(G)f(v) and the minimum weight of a Roman {3}-dominating function on G is called the Roman{3}-domination number of G and is denoted by γ{R3}(G). Given a graph G, Roman{3}-domination asks to find the minimum weight of a Roman {3}-dominating function on G. In this paper, we study the algorithmic aspects of Roman{3}-domination on various graph classes. We show that the decision version of Roman{3}-domination remains NP-complete for chordal bipartite graphs, planar graphs, star-convex bipartite graphs, and chordal graphs. We show that Roman{3}-domination cannot be approximated within a ratio of (13−ɛ)ln|V(G)| for any ɛ>0 unless P=NP for bipartite graphs as well as chordal graphs, whereas Roman{3}-domination can be approximated within a factor of O(lnΔ) for graphs having maximum degree Δ. We also show that Roman{3}-domination is APX-complete for graphs with maximum degree 4. On the positive side, we show that Roman{3}-domination can be solved in linear time for chain graphs and cographs.
This book includes 15 articles published in the Special Issue "Theoretical Computer Science and Discrete Mathematics" of Symmetry (ISSN 2073-8994). This Special Issue is devoted to original and ...significant contributions to theoretical computer science and discrete mathematics. The aim was to bring together research papers linking different areas of discrete mathematics and theoretical computer science, as well as applications of discrete mathematics to other areas of science and technology. The Special Issue covers topics in discrete mathematics including (but not limited to) graph theory, cryptography, numerical semigroups, discrete optimization, algorithms, and complexity.
Roman {2}-domination Chellali, Mustapha; Haynes, Teresa W.; Hedetniemi, Stephen T. ...
Discrete Applied Mathematics,
05/2016, Letnik:
204
Journal Article
Recenzirano
Odprti dostop
In this paper, we initiate the study of a variant of Roman dominating functions. For a graph G=(V,E), a Roman {2}-dominating function f:V→{0,1,2} has the property that for every vertex v∈V with ...f(v)=0, either v is adjacent to a vertex assigned 2 under f, or v is adjacent to least two vertices assigned 1 under f. The weight of a Roman {2}-dominating function is the sum ∑v∈Vf(v), and the minimum weight of a Roman {2}-dominating function f is the Roman {2}-domination number. First, we present bounds relating the Roman {2}-domination number to some other domination parameters. In particular, we show that the Roman {2}-domination number is bounded above by the 2-rainbow domination number. Moreover, we prove that equality between these two parameters holds for trees and cactus graphs with no even cycles. Finally, we show that associated decision problem for Roman {2}-domination is NP-complete, even for bipartite graphs.
The k-component domination number γk(G) of G is the minimum cardinality of a dominating set S of G such that each component of GS has order at least k. Clearly, γ1(G) is the domination number of G ...and γ2(G) is the total domination number of G. With a finite set of exceptional graphs, McCuaig and Shepherd (1989) 13 proved that γ1(G)≤25n and Henning (2000) 11 proved that γ2(G)≤47n respectively. As an extension, Alvarado et al. (2016) 1 posed a conjecture which says that if G is a connected graph of order n≥k+1 and δ(G)≥2, then γk(G)≤2kn2k+3 unless G belongs to a set of exceptional graphs. In this paper, we confirm the validity of the above conjecture. Moreover, we characterize those graphs of order n which are edge-minimal with respect to satisfying G connected, δ(G)≥2 and γk(G)≥2kn2k+3. This strengthens a result of Alvarado, Dantas, and Rautenbach in the same paper.
Double Roman domination Beeler, Robert A.; Haynes, Teresa W.; Hedetniemi, Stephen T.
Discrete Applied Mathematics,
10/2016, Letnik:
211
Journal Article
Recenzirano
Odprti dostop
For a graph G=(V,E), a double Roman dominating function is a function f:V→{0,1,2,3} having the property that if f(v)=0, then vertex v must have at least two neighbors assigned 2 under f or one ...neighbor with f(w)=3, and if f(v)=1, then vertex v must have at least one neighbor with f(w)≥2. The weight of a double Roman dominating function f is the sum f(V)=∑v∈Vf(v), and the minimum weight of a double Roman dominating function on G is the double Roman domination number of G. We initiate the study of double Roman domination and show its relationship to both domination and Roman domination. Finally, we present an upper bound on the double Roman domination number of a connected graph G in terms of the order of G and characterize the graphs attaining this bound.
Perfect Italian domination in cographs Banerjee, S.; Henning, Michael A.; Pradhan, D.
Applied mathematics and computation,
02/2021, Letnik:
391
Journal Article
Recenzirano
•We study the perfect Italian domination problem on cographs.•For a connected cograph G of order n ≥ 1, γIp(G)∈{1,2,3,4} or γIp(G)=n.•There is no connected cograph with γIp(G)=k, where k ∈ {5, 6, ...7, 8, 9}.•A linear time algorithm that computes γIp(G) for a cograph G is proposed.
For a graph G=(VG,EG), a perfect Italian dominating function on G is a function g: VG → {0, 1, 2} satisfying the condition that for each vertex v with g(v)=0, the sum of the function values assigned to the neighbors of v is exactly two, that is, ∑g(u)=2 where the sum is taken over all neighbors of v. The weight of g, denoted by w(g) is defined ∑g(v) where the sum is taken over all v ∈ VG. The perfect Italian domination number of G, denoted γIp(G), is the minimum weight of a perfect Italian dominating function of G. In this paper, we prove that the perfect Italian domination number of a connected cograph, a graph containing no induced path on four vertices, belongs to {1, 2, 3, 4} or equals to the order of the cograph. We prove that there is no connected cograph with perfect Italian domination number k, where k ∈ {5, 6, 7, 8, 9}. We also show that for any positive integer k, k ∉ {5, 6, 7, 8, 9}, there exists a connected cograph whose perfect Italian domination number is k. Moreover, we devise a linear time algorithm that computes the perfect Italian domination number in cographs.
Let G=(V,E) be a graph, a set S⊆V is a total k-dominating set if every vertex v∈V has at least k neighbors in S. The total k-domination number γkt(G) is the minimum cardinality among all total ...k-dominating sets. In this paper, we obtain several tight bounds for the total k-domination number of the strong product of two graphs. In particular, we investigate the relationship between the total k-domination number of the strong product of two graphs with the domination, k-domination and total k-domination numbers of the factors in the product.
Triple Roman domination in graphs Abdollahzadeh Ahangar, H.; Álvarez, M.P.; Chellali, M. ...
Applied mathematics and computation,
02/2021, Letnik:
391
Journal Article
Recenzirano
The Roman domination in graphs is well-studied in graph theory. The topic is related to a defensive strategy problem in which the Roman legions are settled in some secure cities of the Roman Empire. ...The deployment of the legions around the Empire is designed in such a way that a sudden attack to any undefended city could be quelled by a legion from a strong neighbour. There is an additional condition: no legion can move if doing so leaves its base city defenceless. In this manuscript we start the study of a variant of Roman domination in graphs: the triple Roman domination. We consider that any city of the Roman Empire must be able to be defended by at least three legions. These legions should be either in the attacked city or in one of its neighbours. We determine various bounds on the triple Roman domination number for general graphs, and we give exact values for some graph families. Moreover, complexity results are also obtained.
PDF
