MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

Consider the bipartite graph whose partite sets are two disjoint copies of $\{0,1\}^n$, with an edge joining $u$ and $v$ if and only if there is no position in which both $u$ and $v$ have $1$; that is, no carrying occurs if $u$ and $v$ are added as binary numbers. Up to the edge joining the two zeroes, this graph is a double cover of the graph on the vertex set $\{0,1\}^n$ in which two vertices are adjacent whenever they meet the condition just mentioned.

The graph just described has $2^{n+1}$ vertices and $3^n$ edges; for $n=1$ it is just the path of length $4$.

My question is: Has this graph ever been studied? Does it have a name?


Addressing Zsb√°n's (highly relevant) remark, here is, essentially, a re-statement of my question.

The Kneser graph $KG_{n,k}$ is the graph whose vertices are the $k$-element subsets of a fixed $n$-element set, with two vertices adjacent whenever the corresponding subsets are disjoint. What if we consider instead the graph whose vertices are all subsets of our $n$-element set (and the adjacency condition is left intact)? Has this graph been studied? Does it have a name?

share|cite|improve this question
I don't know if it has a name, but the definition is distantly related to that of the Kneser graphs. – Zsbán Ambrus Mar 22 '11 at 11:06
I may have missed it, but I couldn't find it in the ISGCI list of 8-node graphs (for the case $n=2$). – Anthony Labarre Mar 22 '11 at 12:27

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.