Let $Q_n$ be a hypercube graph and $\phi: Q_n\to G$ a surjective simplicial graph morphism i.e. if $u,v$ are adjacent vertices in $Q_n$ then either $\phi(u)=\phi(v)$ or $\phi(u),\phi(v)$ are adjacent. Is there any intrinsic characterization of graphs $G$ which can be the image of such a map?
0

4$\begingroup$ If you consider the vertices of $Q_n$ as binary strings, you can map all the strings of the same weight (number of 1's) together to create a path. A homomorphic image of a path can be anything, so you can get any graph as a homomorphic image of $Q_n$ if you do not restrict $n$. If $n$ is fixed then it is not so clear. Here is a paper about homomorphisms from $Q_n$ to the infinite path, but they are focused on the diameter of the image, which may not be useful to you. Also, they don't allow adjacent vertices to be mapped together. $\endgroup$ – David Roberson Oct 15 '15 at 19:01

1$\begingroup$ The fixed $n$ question actually seems more natural in the reverse direction: For any graph $G$, we can define the "hypercube number" (for lack of a better term) as the smallest $n$ for which the graph is a homomorphic image of $Q_n$. What can be said about the hypercube number of a graph, and can it be bounded in terms of other graph properties? $\endgroup$ – Kevin P. Costello Oct 15 '15 at 21:04

$\begingroup$ Your question is unclear to me: I think $u$ and $v$ should be vertices of $Q_n$, not $G$? Can you clarify the properties of the morphism you are looking for? It seems not to be a standard graph homomorphism. $\endgroup$ – Florent Foucaud Oct 20 '15 at 9:39

$\begingroup$ @DavidE.Roberson I'm not sure I understand your comment. Yes a homomorphic image of a path can be anything but being inside a cube puts further restrictions on the image. For example you can map a spanning path in a 3cube to a heptagon but the adjacency relations imposed by the cube and the definition of a graph map imply that the image cannot be longer than a 4cycle. $\endgroup$ – Reza Rezazadegan Feb 29 '16 at 16:05

$\begingroup$ Or in other words: what about the vertices that are not in the path? $\endgroup$ – Reza Rezazadegan Feb 29 '16 at 16:27