Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userThe k-Power Domination Number in Some Self-Similar Graphs
117
0
0.0
(
0
)
Added by
Yulun Xu
Publication date
2019
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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.
A graph $G$ is $k$-vertex-critical if $G$ has chromatic number $k$ but every proper induced subgraph of $G$ has chromatic number less than $k$. The study of $k$-vertex-critical graphs for graph classes is an important topic in algorithmic graph theory because if the number of such graphs that are in a given hereditary graph class is finite, then there is a polynomial-time algorithm to decide if a graph in the class is $(k-1)$-colorable. In this paper, we prove that for every fixed integer $kge 1$, there are only finitely many $k$-vertex-critical ($P_5$,gem)-free graphs and $(P_5,overline{P_3+P_2})$-free graphs. To prove the results we use a known structure theorem for ($P_5$,gem)-free graphs combined with properties of $k$-vertex-critical graphs. Moreover, we characterize all $k$-vertex-critical ($P_5$,gem)-free graphs and $(P_5,overline{P_3+P_2})$-free graphs for $k in {4,5}$ using a computer generation algorithm.
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.
We show that every n-vertex cubic graph with girth at least g have domination number at most 0.299871n+O(n/g)<3n/10+O(n/g).
A $k$-tuple total dominating set ($k$TDS) of a graph $G$ is a set $S$ of vertices in which every vertex in $G$ is adjacent to at least $k$ vertices in $S$. The minimum size of a $k$TDS is called the $k$-tuple total dominating number and it is denoted by $gamma_{times k,t}(G)$. We give a constructive proof of a general formula for $gamma_{times 3, t}(K_n Box K_m)$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
