The independent domination number $i(G)$ (independent number $\beta (G)$) is the minimum (maximum) cardinality among all maximal independent sets of $G$. Haviland (1995) conjectured that any connected regular graph $G$ of order $n$ and degree $\delta \le \frac{1}{2}{n}$ satisfies $i(G)\le \lceil \frac{2n}{3\delta }\rceil \frac{1}{2}{\delta }$. For $1\le k\le l\le m$, the subset graph $S_{m}(k,l)$ is the bipartite graph whose vertices are the $k$- and $l$-subsets of an $m$ element ground set where two vertices are adjacent if and only if one subset is contained in the other. In this paper, we give a sharp upper bound for $i(S_{m}(k,l))$ and prove that if $k+l=m$ then Haviland’s conjecture holds for the subset graph $S_{m}(k,l)$. Furthermore, we give the exact value of $\beta (S_{m}(k,l))$.
Let $G=(V, E)$ be a simple graph. A subset $S\subseteq V$ is a dominating set of $G$, if for any vertex $u\in V-S$, there exists a vertex $v\in S$ such that $uv\in E$. The domination number, denoted by $\gamma (G)$, is the minimum cardinality of a dominating set. In this paper we will prove that if $G$ is a 5-regular graph, then $\gamma (G)\le {5\over 14}n$.
A dominating set in a graph $G$ is a connected dominating set of $G$ if it induces a connected subgraph of $G$. The minimum number of vertices in a connected dominating set of $G$ is called the connected domination number of $G$, and is denoted by $\gamma _{c}(G)$. Let $G$ be a spanning subgraph of $K_{s,s}$ and let $H$ be the complement of $G$ relative to $K_{s,s}$; that is, $K_{s,s}=G\oplus H$ is a factorization of $K_{s,s}$. The graph $G$ is $k$-$\gamma _{c}$-critical relative to $K_{s,s}$ if $\gamma _{c}(G)=k$ and $\gamma _{c}(G+e)<k$ for each edge $e\in E(H)$. First, we discuss some classes of graphs whether they are $\gamma _{c}$-critical relative to $K_{s,s}$. Then we study $k$-$\gamma _{c}$-critical graphs relative to $K_{s,s}$ for small values of $k$. In particular, we characterize the $3$-$\gamma _{c}$-critical and $4$-$\gamma _{c}$-critical graphs.
We initiate the study of signed majority total domination in graphs. Let $G=(V,E)$ be a simple graph. For any real valued function $f\: V \rightarrow \mathbb{R}$ and ${S\subseteq V}$, let $f(S)=\sum _{v\in S}f(v)$. A signed majority total dominating function is a function $f\: V\rightarrow \lbrace -1,1\rbrace $ such that $f(N(v))\ge 1$ for at least a half of the vertices $v\in V$. The signed majority total domination number of a graph $G$ is $\gamma _{{\mathrm maj}}^{{\,\mathrm t}}(G)=\min \lbrace f(V)\mid f$ is a signed majority total dominating function on $G\rbrace $. We research some properties of the signed majority total domination number of a graph $G$ and obtain a few lower bounds of $\gamma _{{\mathrm maj}}^{{\,\mathrm t}}(G)$.
In this paper we initiate the study of total restrained domination in graphs. Let $G=(V,E)$ be a graph. A total restrained dominating set is a set $S\subseteq V$ where every vertex in $V-S$ is adjacent to a vertex in $S$ as well as to another vertex in $V-S$, and every vertex in $S$ is adjacent to another vertex in $S$. The total restrained domination number of $G$, denoted by $\gamma _r^t(G)$, is the smallest cardinality of a total restrained dominating set of $G$. First, some exact values and sharp bounds for $\gamma _r^t(G)$ are given in Section 2. Then the Nordhaus-Gaddum-type results for total restrained domination number are established in Section 3. Finally, we show that the decision problem for $\gamma _r^t(G)$ is NP-complete even for bipartite and chordal graphs in Section 4.
A set $S$ of vertices in a graph $G$ is called a paired-dominating set if it dominates $V$ and $\langle S\rangle $ contains at least one perfect matching. We characterize the set of vertices of a tree that are contained in all minimum paired-dominating sets of the tree.