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.
If $x$ is a vertex of a digraph $D$, then we denote by $d^+(x)$ and $d^-(x)$ the outdegree and the indegree of $x$, respectively. A digraph $D$ is called regular, if there is a number $p \in \mathbb{N}$ such that $d^+(x) = d^-(x) = p$ for all vertices $x$ of $D$. A $c$-partite tournament is an orientation of a complete $c$-partite graph. There are many results about directed cycles of a given length or of directed cycles with vertices from a given number of partite sets. The idea is now to combine the two properties. In this article, we examine in particular, whether $c$-partite tournaments with $r$ vertices in each partite set contain a cycle with exactly $r-1$ vertices of every partite set. In 1982, Beineke and Little [2] solved this problem for the regular case if $c = 2$. If $c \ge 3$, then we will show that a regular $c$-partite tournament with $r \ge 2$ vertices in each partite set contains a cycle with exactly $r-1$ vertices from each partite set, with the exception of the case that $c = 4$ and $r = 2$.
A perfect independent set I of a graph G is defined to be an independent set with the property that any vertex not in I has at least two neighbors in I. For a nonnegative integer k, a subset I of the vertex set V (G) of a graph G is said to be k-independent, if I is independent and every independent subset I' of G with |I' | ≥ |I| − (k − 1) is a subset of I. A set I of vertices of G is a super k-independent set of G if I is k-independent in the graph G[I, V (G) − I], where G[I, V (G) − I] is the bipartite graph obtained from G by deleting all edges which are not incident with vertices of I. It is easy to see that a set I is 0-independent if and only if it is a maximum independent set and 1-independent if and only if it is a unique maximum independent set of G. In this paper we mainly investigate connections between perfect independent sets and k-independent as well as super k-independent sets for k = 0 and k = 1.
A graph $G$ is a $\lbrace d,d+k\rbrace $-graph, if one vertex has degree $d+k$ and the remaining vertices of $G$ have degree $d$. In the special case of $k=0$, the graph $G$ is $d$-regular. Let $k,p\ge 0$ and $d,n\ge 1$ be integers such that $n$ and $p$ are of the same parity. If $G$ is a connected $\lbrace d,d+k\rbrace $-graph of order $n$ without a matching $M$ of size $2|M|=n-p$, then we show in this paper the following: If $d=2$, then $k\ge 2(p+2)$ and (i) $n\ge k+p+6$. If $d\ge 3$ is odd and $t$ an integer with $1\le t\le p+2$, then (ii) $n\ge d+k+1$ for $k\ge d(p+2)$, (iii) $n\ge d(p+3)+2t+1$ for $d(p+2-t)+t\le k\le d(p+3-t)+t-3$, (iv) $n\ge d(p+3)+2p+7$ for $k\le p$. If $d\ge 4$ is even, then (v) $n\ge d+k+2-\eta $ for $k\ge d(p+3)+p+4+\eta $, (vi) $n\ge d+k+p+2-2t=d(p+4)+p+6$ for $k=d(p+3)+4+2t$ and $p\ge 1$, (vii) $n\ge d+k+p+4$ for $d(p+2)\le k\le d(p+3)+2$, (viii) $n\ge d(p+3)+p+4$ for $k\le d(p+2)-2$, where $0\le t\le \frac{1}{2}{p}-1$ and $\eta =0$ for even $p$ and $0\le t\le \frac{1}{2}(p-1)$ and $\eta =1$ for odd $p$. The special case $k=p=0$ of this result was done by Wallis [6] in 1981, and the case $p=0$ was proved by Caccetta and Mardiyono [2] in 1994. Examples show that the given bounds (i)–(viii) are best possible.
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)$.