Let $G$ be a graph with vertex set $V(G)$, and let $k\ge 1$ be an integer. A subset $D \subseteq V(G)$ is called a {\it $k$-dominating set} if every vertex $v\in V(G)-D$ has at least $k$ neighbors in $D$. The $k$-domination number $\gamma _k(G)$ of $G$ is the minimum cardinality of a $k$-dominating set in $G$. If $G$ is a graph with minimum degree $\delta (G)\ge k+1$, then we prove that $$\gamma _{k+1}(G)\le \frac {|V(G)|+\gamma _k(G)}2.$$ In addition, we present a characterization of a special class of graphs attaining equality in this inequality.
Let (G) and i(G) be the domination number and the independent domination number of G, respectively. Rad and Volkmann posted a conjecture that i(G)/ (G) 6 (G)/2 for any graph G, where (G) is its maximum degree (see N. J.Rad, L.Volkmann (2013)). In this work, we verify the conjecture for bipartite graphs. Several graph classes attaining the extremal bound and graphs containing odd cycles with the ratio larger than (G)/2 are provided as well., Shaohui Wang, Bing Wei., and Seznam literatury
The k-core of a graph G, Ck(G), is the maximal induced subgraph H ⊆ G such that δ(G) ≥ k, if it exists. For k > 0, the k-shell of a graph G is the subgraph of G induced by the edges contained in the k-core and not contained in the (k + 1)-core. The core number of a vertex is the largest value for k such that v ∈ Ck(G), and the maximum core number of a graph, Cb(G), is the maximum of the core numbers of the vertices of G. A graph G is k-monocore if Cb(G) = δ(G) = k. This paper discusses some basic results on the structure of k-cores and k-shells. In particular, an operation characterization of 2-monocore graphs is proven. Some applications of cores and shells to graph coloring and domination are considered.
For a graphical property P and a graph G, a subset S of vertices of G is a P-set if the subgraph induced by S has the property P. The domination number with respect to the property P, is the minimum cardinality of a dominating P-set. In this paper we present results on changing and unchanging of the domination number with respect to the nondegenerate and hereditary properties when a graph is modified by adding an edge or deleting a vertex.
Given two disjoint copies of a graph $G$, denoted $G^1$ and $G^2$, and a permutation $\pi $ of $V(G)$, the graph $\pi G$ is constructed by joining $u \in V(G^1)$ to $\pi (u) \in V(G^2)$ for all $u \in V(G^1)$. $G$ is said to be a universal fixer if the domination number of $\pi G$ is equal to the domination number of $G$ for all $\pi $ of $V(G)$. In 1999 it was conjectured that the only universal fixers are the edgeless graphs. Since then, a few partial results have been shown. In this paper, we prove the conjecture completely.
A graph is 2-stratified if its vertex set is partitioned into two classes, where the vertices in one class are colored red and those in the other class are colored blue. Let F be a 2-stratified graph rooted at some blue vertex v. An F-coloring of a graph G is a red-blue coloring of the vertices of G in which every blue vertex v belongs to a copy of F rooted at v. The F-domination number γF (G) is the minimum number of red vertices in an F-coloring of G. In this paper, we study F-domination where F is a red-blue-blue path of order 3 rooted at a blue end-vertex. It is shown that a triple (A, B, C) of positive integers with A ≤ B ≤ 2A and B ≥ 2 is realizable as the domination number, open domination number, and F-domination number, respectively, for some connected graph if and only if (A, B, C) ≠ (k, k, C) for any integers k and C with C > k ≥ 2.
Let $k$ be a positive integer, and let $G$ be a simple graph with vertex set $V(G)$. A {\it $k$-dominating set} of the graph $G$ is a subset $D$ of $V(G)$ such that every vertex of $V(G)-D$ is adjacent to at least $k$ vertices in $D$. A {\it $k$-domatic partition} of $G$ is a partition of $V(G)$ into $k$-dominating sets. The maximum number of dominating sets in a $k$-domatic partition of $G$ is called the {\it $k$-domatic number} $d_k(G)$. \endgraf In this paper, we present upper and lower bounds for the $k$-domatic number, and we establish Nordhaus-Gaddum-type results. Some of our results extend those for the classical domatic number $d(G)=d_1(G)$.