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?

  • 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 3-cube 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 4-cycle. $\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

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.