Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
Perhaps you could edit the meaning of $a(G)$ into your question. – Gerry Myerson May 9 '12 at 12:58
α(G) is the independence number of G – James Alex May 9 '12 at 14:07
I'm not sure I'm understanding the question properly. Can you clarify why the graph $G$ consisting of a 3-cycle and a 4-cycle would not be a counterexample? It would seem to satisfy $n=3$, $p=7$, but it is obviously not a $3K_3$. – Will Orrick May 10 '12 at 16:48
@WillOrrick The graph you mentioned is 2 regular, not (7-3)=4 regular. – Graphth May 10 '12 at 20:20
@Graphth : Hmmm. I had understood that it was $\overline{G}$ that was required to be $(p-n)$-regular, rather than $G$. Perhaps this is the root of my confusion. I'm now not sure that I understand how $3K_3$ is defined. Wouldn't $p$ equal 9 in that case, and $G$ have to be 6-regular? – Will Orrick May 10 '12 at 21:41

(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$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.