0
$\begingroup$

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?

$\endgroup$
6
  • 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$ Oct 15, 2015 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$ Oct 15, 2015 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$ Oct 20, 2015 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$ Feb 29, 2016 at 16:05
  • $\begingroup$ Or in other words: what about the vertices that are not in the path? $\endgroup$ Feb 29, 2016 at 16:27

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.