Dominating set for a graph $G=(V,E)$ is a subset $D$ of $V$ such that every vertex not in $D$ is adjacent to at least one member of $D$. The domination number $γ(G)$ is the number of vertices in a smallest dominating set for $G$.

Independent set is also a dominating set if and only if it is a maximal independent set, so any maximal independent set in a graph is necessarily also a minimal dominating set. Thus, the smallest maximal independent set is greater in size than the smallest independent dominating set. The independent domination number $i(G)$ of a graph GG is the size of the smallest independent dominating set (or, equivalently, the size of the smallest maximal independent set).

i need a connected graph $G=(V,E)$ with chromatic number greater than or equal to $3$ such that $i(G)>((3/4)V)−2$ or $i(G)>((2/3)V)−1$.

Can you help me?

  • $\begingroup$ By $(3/4)V$ you mean $(3/4)|V|$? I.e., $V$ denotes both the set of vertices and the number of vertices? $\endgroup$
    – bof
    Mar 5, 2016 at 6:47

1 Answer 1


Let $V=V_1\cup V_2\cup V_3\cup V_4\cup V_5$ where $V_1,V_2,V_3,V_4,V_5$ are pairwise disjoint $12$-element sets. Choose a vertex $u_i\in V_i$ for each $i,$ and let $E$ consist of the edges $u_iv\ (u_i\ne v\in V_i)$ and the edges $u_iu_j\ (i\ne j).$

Then $G=(V,E)$ is a connected graph with $\chi(G)=5,\ |V|=60,\ |E|=65,$ and $i(G)=45=\frac34|V|.$

This example can obviously be modified to get $i(G)\gt\alpha|V|$ for any given $\alpha\lt1.$


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .