0
$\begingroup$

I am working on the statement " A graph $G$ is a $nKn$ (collection of $n$ number of complete graph each of order $n$) graph if and only if $\bar{G}$ is $α(G) = α(\bar{G}) = n$ and $(p-n)$-regular , where $p$ is the order of $G$ and $α(G)$ is the independence number of $G$ with $n\geqslant 1$."

The converse part seem to be a confusion. Kindly help me with it.

  • 0
    @Brian: Thanks for confirming that. I hope that the OP will clarify.2012-05-12

1 Answers 1

1

(Extended compilation of comments.)

While it is true that the disjoint union of $n$ copies of $K_n$ has the properties

  1. $\alpha(G)=\alpha(\overline G)=n$ (where $\alpha$ is the independence number)
  2. $\overline{G}$ is $p-n$ regular (where $p$ is the number of vertices of $G$)

the converse is not true. not every graph with properties 1 and 2. Will Orrick gave the following counterexample in comments: let $G$ be the disjoint union of two cycles $C_3 $ and $C_4$; then $\alpha(G)=\alpha(\overline G)=3$ and $\overline{G}$ is $4$-regular where $4=7-3$.

Brian M. Scott then observed that if $\alpha(\overline G)=n$ is strengthened to

(*) every maximal independent set in $\overline G$ has cardinality $n$

then the conclusion $G=nK_n$ follows. Indeed, (*) says that every maximal clique of $G$ has cardinality $n$. Therefore, every vertex is contained in a copy of $K_n$. Since $G$ is $n$-regular (by virtue of 2), it is a disjoint union of some copies of $K_n$. The condition $\alpha(G)=n$ places the number of the copies of $K_n$ at $n$.