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?

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.