MathOverflow is a question and answer site for professional mathematicians. 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

In Shannon's paper, "The Zero Error Capacity of a Noisy Channel", he says that the Shannon capacity of all graphs of order 6 are determined, except for four exceptions. That is, for all but the four exceptions, we have $\alpha(G) = \chi(\bar{G})$. He says the four exceptions "can be given in terms of the capacity of [the 5-cycle]." I want to understand this better.

By the way, I think in terms of the Shannon capacity as $\Theta(G) = \sup_k \sqrt[k]{\alpha(G^k)}$, whereas Shannon considered the log of this in his paper. Note, $G^k$ denotes the strong product of $k$ copies of $G$.

One of the four exceptions is $C_5 + K_1$, a disjoint union. We have $\Theta(C_5 + K_1) \geq \Theta(C_5) + \Theta(K_1)$. But, I read in a paper by Alon that if $\alpha(G) = \Theta(G)$ for one of the two graphs in the sum, then we have in fact equality. So, here we would have equality, so that $\Theta(C_5 + K_1) = \sqrt{5} + 1$. I get that then. So, my question is with the three remaining graphs.

One graph would be the wheel on 6 vertices, $W_6 = C_5 \vee K_1$, where $\vee$ means the graph join. The other two graphs would be spanning subgraphs of these. Delete one spoke of the wheel to get one. Delete a neighboring spoke, of the first deleted spoke, to get the next. Now that we know $\Theta(C_5) = \sqrt{5}$, how do we determine $\Theta(W_6)$ and $\Theta$ of the other two exceptions?

share|cite|improve this question
Probably your question would be a bit more friendly if you defined the functions $\alpha(G)$, $\chi(\bar G)$ etc. – Anthony Quas Dec 11 '12 at 20:14
@anthony $\alpha(G)$ is the independence number, the largest set of vertices such that none are adjacent to each other. $\chi(G)$ is the chromatic number of $G$, the least number of colors needed to color the vertices of $G$ such that no two adjacent vertices are colored the same. $\bar{G}$ is the complement of $G$, so that $v_i$ is adjacent to $v_j$ in $G$ if and only if $v_i$ is not adjacent to $v_j$ in $\bar{G}$. – Graphth Dec 11 '12 at 20:49
There's still something missing here. Say the independence number of $G$ is $2$. $\sup_k\root k\of2$ is infinite; $\root k\of2\to\infty$ as $k\to0^+$. – Gerry Myerson Dec 11 '12 at 22:15
@gerry Yup, sorry about that. I had a typo in my definition of the Shannon capacity. Fixed it, thanks for your tip. – Graphth Dec 11 '12 at 23:21

Your Answer


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

Browse other questions tagged or ask your own question.