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, 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.
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.
A philosophical exploration of female submission, using insights from feminist thinkers—especially Simone de Beauvoir—to reveal the complexities of women's reality and lived experience What role do ...women play in the perpetuation of patriarchy? On the one hand, popular media urges women to be independent, outspoken, and career-minded. Yet, this same media glorifies a specific, sometimes voluntary, female submissiveness as a source of satisfaction. In philosophy, even less has been said on why women submit to men and the discussion has been equally contradictory—submission has traditionally been considered a vice or pathology, but female submission has been valorized as innate to women's nature. Is there a way to explore female submission in all of its complexity—not denying its appeal in certain instances, and not buying into an antifeminist, sexist, or misogynistic perspective? We Are Not Born Submissive offers the first in-depth philosophical exploration of female submission, focusing on the thinking of Simone de Beauvoir, and more recent work in feminist philosophy, epistemology, and political theory. Manon Garcia argues that to comprehend female submission, we must invert how we examine power and see it from the woman's point of view. Historically, philosophers, psychoanalysts, and even some radical feminists have conflated femininity and submission. Garcia demonstrates that only through the lens of women's lived experiences—their economic, social, and political situations—and how women adapt their preferences to maintain their own well-being, can we understand the ways in which gender hierarchies in society shape women's experiences. Ultimately, she asserts that women do not actively choose submission. Rather, they consent to—and sometimes take pleasure in—what is prescribed to them through social norms within a patriarchy.Moving beyond the simplistic binary of natural destiny or moral vice, We Are Not Born Submissive takes a sophisticated look at how female submissiveness can be explained.
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.
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
