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.
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.
Roman {2}-domination Chellali, Mustapha; Haynes, Teresa W.; Hedetniemi, Stephen T. ...
Discrete Applied Mathematics,
05/2016, Volume:
204
Journal Article
Peer reviewed
Open access
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, Volume:
211
Journal Article
Peer reviewed
Open access
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, Volume:
391
Journal Article
Peer reviewed
•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, Volume:
391
Journal Article
Peer reviewed
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.
In this paper, we study the most basic domination invariants in graphs, in which number 2 is intrinsic part of their definitions. We classify them upon three criteria, two of which give the following ...previously studied invariants: the weak 2-domination number, γw2(G), the 2-domination number, γ2(G), the {2}-domination number, γ{2}(G), the double domination number, γ×2(G), the total {2}-domination number, γt{2}(G), and the total double domination number, γt×2(G), where G is a graph in which the corresponding invariant is well defined. The third criterion yields rainbow versions of the mentioned six parameters, one of which has already been well studied, and three other give new interesting parameters. Together with a special, extensively studied Roman domination, γR(G), and two classical parameters, the domination number, γ(G), and the total domination number, γt(G), we consider 13 domination invariants in graphs. In the main result of the paper we present sharp upper and lower bounds of each of the invariants in terms of every other invariant, a large majority of which are new results proven in this paper. As a consequence of the main theorem we obtain new complexity results regarding the existence of approximation algorithms for the studied invariants, matched with tight or almost tight inapproximability bounds, which hold even in the class of split graphs.
PDF
