Timeline for Is there any result on the homomorphic images of hypercube graphs?
Current License: CC BY-SA 3.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 1, 2016 at 16:28 | comment | added | David Roberson | @RezaRezazadegan I do not mean that if you map a path from within an $n$-cube to a graph then it can be extended to the whole $n$-cube. As you point out, that is not always possible. What I meant is that you can map the entire $n$-cube to a path (of length $n$). Since the homomorphic image of a path can be anything, you can compose the map from the cube to the path with the map from the path to the anything to obtain a map from the cube to the anything. | |
| Feb 29, 2016 at 16:27 | comment | added | Reza Rezazadegan | Or in other words: what about the vertices that are not in the path? | |
| Feb 29, 2016 at 16:05 | comment | added | Reza Rezazadegan | @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. | |
| Nov 19, 2015 at 22:15 | history | edited | user9072 |
edited tags
|
|
| Oct 21, 2015 at 11:52 | history | edited | Reza Rezazadegan | CC BY-SA 3.0 |
added 2 characters in body
|
| Oct 20, 2015 at 9:39 | comment | added | Florent Foucaud | 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. | |
| Oct 15, 2015 at 21:04 | comment | added | Kevin P. Costello | 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? | |
| Oct 15, 2015 at 19:01 | comment | added | David Roberson | 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. | |
| Oct 15, 2015 at 18:21 | history | edited | Reza Rezazadegan | CC BY-SA 3.0 |
added 11 characters in body
|
| Oct 15, 2015 at 18:07 | history | asked | Reza Rezazadegan | CC BY-SA 3.0 |