Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userEdge Domination Number and the Number of Minimum Edge Dominating Sets in Pseudofractal Scale-Free Web and Sierpinski Gasket
134
0
0.0
(
0
)
Added by
Xiaotian Zhou
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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.
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.
We study the number of connected spanning subgraphs $f_{d,b}(n)$ on the generalized Sierpinski gasket $SG_{d,b}(n)$ at stage $n$ with dimension $d$ equal to two, three and four for $b=2$, and layer $b$ equal to three and four for $d=2$. The upper and lower bounds for the asymptotic growth constant, defined as $z_{SG_{d,b}}=lim_{v to infty} ln f_{d,b}(n)/v$ where $v$ is the number of vertices, on $SG_{2,b}(n)$ with $b=2,3,4$ are derived in terms of the results at a certain stage. The numerical values of $z_{SG_{d,b}}$ are obtained.
Let $T$ be a rooted tree, and $V(T)$ its set of vertices. A subset $X$ of $V(T)$ is called an infima closed set of $T$ if for any two vertices $u,vin X$, the first common ancestor of $u$ and $v$ is also in $X$. This paper determines the trees with minimum number of infima closed sets among all rooted trees of given order, thereby answering a question of Klazar. It is shown that these trees are essentially complete binary trees, with the exception of vertices at the last levels. Moreover, an asymptotic estimate for the minimum number of infima closed sets in a tree with $n$ vertices is also provided.
In this paper, we study independent domination in directed graphs, which was recently introduced by Cary, Cary, and Prabhu. We provide a short, algorithmic proof that all directed acyclic graphs contain an independent dominating set. Using linear algebraic tools, we prove that any strongly connected graph with even period has at least two independent dominating sets, generalizing several of the results of Cary, Cary, and Prabhu. We prove that determining the period of the graph is not sufficient to determine the existence of an independent dominating set by constructing a few examples of infinite families of graphs. We show that the direct analogue of Vizings Conjecture does not hold for independent domination number in directed graphs by providing two infinite families of graphs. We initialize the study of time complexity for independent domination in directed graphs, proving that the existence of an independent dominating set in directed acyclic graphs and strongly connected graphs with even period are in the time complexity class $P$. We also provide an algorithm for determining existence of an independent dominating set for digraphs with period greater than $1$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
