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
    Perhaps you could edit the meaning of $a(G)$ into your question.2012-05-09
  • 0
    α(G) is the independence number of G2012-05-09
  • 0
    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$.2012-05-10
  • 0
    @WillOrrick The graph you mentioned is 2 regular, not (7-3)=4 regular.2012-05-10
  • 0
    @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?2012-05-10
  • 0
    @WillOrrick Oh, good point. Yea, I don't understand what the "$\bar{G}$ is" portion refers to at all. I read it without the $\bar{G}$ is" portion. Until the OP tells us what it's supposed to mean, I guess we can't know.2012-05-11
  • 0
    @Graphth : I had assumed that "$\overline{G}$ is..." meant "$\overline{G}$ satisfies $\alpha(\overline{G})=\alpha(G)=n$ and is $(p-n)$-regular". If by "$3K_3$" is meant three disconnected copies of $K_3$, then with $G=3K_3$, we have $p=9$, $\alpha(\overline{G})=\alpha(G)=n=3$ and $\overline{G}$ is 6-regular. So this all seems to fit. But if $G$ consists of a disconnected $C_3$ and $C_4$, then we have $p=7$, $\alpha(\overline{G})=\alpha(G)=n=3$ and $\overline{G}$ is 4-regular, which seems to be a counterexample.2012-05-11
  • 0
    @Will: It certainly is a counterexample to the result as stated. I don't know what was intended, but the result is easy if we strengthen the hypothesis to require that *every* maximal independent set in $\overline{G}$ (and hence every maximal clique in $G$) have cardinality $n$.2012-05-12
  • 0
    @Brian: Thanks for confirming that. I hope that the OP will clarify.2012-05-12

1 Answers 1