Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userUsing edge contractions to reduce the semitotal domination number
110
0
0.0
(
0
)
Added by
Paloma Thome De Lima
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
In this paper, we consider the problem of reducing the semitotal domination number of a given graph by contracting $k$ edges, for some fixed $k geq 1$. We show that this can always be done with at most 3 edge contractions and further characterise those graphs requiring 1, 2 or 3 edge contractions, respectively, to decrease their semitotal domination number. We then study the complexity of the problem for $k=1$ and obtain in particular a complete complexity dichotomy for monogenic classes.
rate research
Read More
As a fundamental research object, the minimum edge dominating set (MEDS) problem is of both theoretical and practical interest. However, determining the size of a MEDS and the number of all MEDSs in a general graph is NP-hard, and it thus makes sense to find special graphs for which the MEDS problem can be exactly solved. In this paper, we study analytically the MEDS problem in the pseudofractal scale-free web and the Sierpinski gasket with the same number of vertices and edges. For both graphs, we obtain exact expressions for the edge domination number, as well as recursive solutions to the number of distinct MEDSs. In the pseudofractal scale-free web, the edge domination number is one-ninth of the number of edges, which is three-fifths of the edge domination number of the Sierpinski gasket. Moreover, the number of all MEDSs in the pseudofractal scale-free web is also less than that corresponding to the Sierpinski gasket. We argue that the difference of the size and number of MEDSs between the two studied graphs lies in the scale-free topology.
The $k$-power domination problem is a problem in graph theory, which has applications in many areas. However, it is hard to calculate the exact $k$-power domination number since determining k-power domination number of a generic graph is a NP-complete problem. We determine the exact $k$-power domination number in two graphs which have the same number of vertices and edges: pseudofractal scale-free web and Sierpinski gasket. The $k$-power domination number becomes 1 for $kge2$ in the Sierpinski gasket, while the $k$-power domination number increases at an exponential rate with regard to the number of vertices in the pseudofractal scale-free web. The scale-free property may account for the difference in the behavior of two graphs.
In this paper, we study the domination number of middle graphs. Indeed, we obtain tight bounds for this number in terms of the order of the graph. We also compute the domination number of some families of graphs such as star graphs, double start graphs, path graphs, cycle graphs, wheel graphs, complete graphs, complete bipartite graphs and friendship graphs, explicitly. Moreover, some Nordhaus-Gaddum-like relations are presented for the domination number of middle graphs.
For a (finite) partially ordered set (poset) $P$, we call a dominating set $D$ in the comparability graph of $P$, an order-sensitive dominating set in $P$ if either $xin D$ or else $a<x<b$ in $P$ for some $a,bin D$ for every element $x$ in $P$ which is neither maximal nor minimal, and denote by $gamma_{os}(P)$, the least size of an order-sensitive dominating set of $P$. For every graph $G$ and integer $kgeq 2$, we associate a graded poset $mathscr{P}_k(G)$ of height $k$, and prove that $gamma_{os}(mathscr{P}_3(G))=gamma_{text{R}}(G)$ and $gamma_{os}(mathscr{P}_4(G))=2gamma(G)$ hold, where $gamma(G)$ and $gamma_{text{R}}(G)$ are the domination and Roman domination number of $G$, respectively. Apart from these, we introduce the notion of a Helly poset, and prove that when $P$ is a Helly poset, the computation of order-sensitive domination number of $P$ can be interpreted as a weighted clique partition number of a graph, the middle graph of $P$. Moreover, we show that the order-sensitive domination number of a poset $P$ exactly corresponds to the biclique vertex-partition number of the associated bipartite transformation of $P$. Finally, we prove that the decision problem of order-sensitive domination on posets of arbitrary height is NP-complete, which is obtained by using a reduction from EQUAL-$3$-SAT problem.
For a graph $G= (V,E)$, a double Roman dominating function (DRDF) is a function $f : V to {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 {at least} one neighbor $u$ with $f (u) = 3$, and if $f (v) = 1$, then vertex $v$ must have at least one neighbor $u$ with $f (u) ge 2$. In this paper, we consider the double Roman domination problem, which is an optimization problem of finding the DRDF $f$ such that $sum_{vin V} f (v)$ is minimum. We propose {five integer linear programming (ILP) formulations and one mixed integer linear programming formulation with polynomial number of constraints for this problem. Some additional valid inequalities and bounds are also proposed for some of these formulations.} Further, we prove that {the first four models indeed solve the double Roman domination problem, and the last two models} are equivalent to the others regardless of the variable relaxation or usage of a smaller number of constraints and variables. Additionally, we use one ILP formulation to give an $H(2(Delta+1))$-approximation algorithm. All proposed formulations and approximation algorithm are evaluated on randomly generated graphs to compare the performance.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
