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?
$\begingroup$
$\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$– David RobersonCommented 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$– Kevin P. CostelloCommented 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$– Florent FoucaudCommented 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$– Reza RezazadeganCommented Feb 29, 2016 at 16:05
-
$\begingroup$ Or in other words: what about the vertices that are not in the path? $\endgroup$– Reza RezazadeganCommented Feb 29, 2016 at 16:27
|
Show 1 more comment