Timeline for Generating short Hamilton cycles from complete graphs
Current License: CC BY-SA 4.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 14, 2021 at 0:51 | answer | added | Max Alekseyev | timeline score: 1 | |
| Oct 13, 2021 at 15:32 | comment | added | Florian Lehner | Here is a variation of @ThomasLesgourgues example: you can pick an arbitrary partition of $V$ into two parts and then delete an edge between the two parts in each step. If the parts are large enough, then this can always be achieved by picking a triangle between them and covering the remainder of each part by a cycle. Eventually there is only one edge left between the two parts, so no Hamilton cycle can be found. | |
| Oct 13, 2021 at 14:10 | comment | added | Max Alekseyev | I missed that $G$ in question is a complete graph. For a non-complete Hamiltonian graph, there exists a counterexample. | |
| Oct 13, 2021 at 14:02 | comment | added | Manfred Weis | @MaxAlekseyev which graph are you referring to; the question asks for starting with a complete graph, which to my knowledge is alsways Hamiltonian? Or do you refer to one of the intermediate graphs that are generated by successive deletion of edges from the original graph? | |
| Oct 13, 2021 at 11:22 | history | edited | Manfred Weis | CC BY-SA 4.0 |
restricted the cycle covers to 2-factors and provided the reason that this restriction is necessary
|
| Oct 13, 2021 at 4:38 | history | edited | Manfred Weis | CC BY-SA 4.0 |
constrained the deletion of cycle edges to those whose deletion from $G$ yields a graph with vertex disjoint cycle cover
|
| Oct 13, 2021 at 4:05 | comment | added | Thomas Lesgourgues | My intuition is that it might be very difficult (if possible at all) to impose a constraint on the deleted edge such that you always encounter a Hamilton cycle. Make me think about some kind of Maker-Breaker game, you play against an opponent, but you can restrict its choices. There might be some intuition to gather from these, but it's not directly related. | |
| Oct 13, 2021 at 2:57 | history | edited | Manfred Weis | CC BY-SA 4.0 |
added a constraint that will yield almost regular intermeditate $G$
|
| Oct 13, 2021 at 2:49 | comment | added | Manfred Weis | By encounter I do indeed mean that one of the generated vertex (disjoint) cycle covers will be a Hamilton cycle; I had in mind a human being that checks the sequence of generated vertex covers. The terminology for the generated subgraphs is very diverse; have also seen "cycle packing"; or "disjoint cycle cover"; I used "vertex disjoint cycle cover" following Bodo Manthey's terminology. Your ounter-example made clear that further constraints must be imposed on the edge that is deleted from the current vertex cycle cover | |
| Oct 12, 2021 at 23:17 | comment | added | Thomas Lesgourgues | What do you mean "encounter" a Hamilton cycle ? That the cycle cover $C$ must be Hamiltonian at one point ? And can you confirm that you are talking about "vertex cycle covers", it seems that edge and vertex covers are both sometimes called "covers". Then surely not, select one vertex $v$. If at each second step, you always delete an edge adjacent to $v$, then you can always find a cycle cover where e.g. $v$ is in a triangle $T$, and all vertices of $G-T$ are in one large cycle (because $G-T$ is complete), up to the point where $v$ has degree $1$, so there is no more cycle cover of $G$. | |
| Oct 11, 2021 at 15:37 | history | asked | Manfred Weis | CC BY-SA 4.0 |