Timeline for Is this graph a hamiltonian graph?
Current License: CC BY-SA 3.0
21 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 26, 2014 at 6:16 | vote | accept | Varaquilex | ||
| Apr 11, 2013 at 15:31 | comment | added | G. Bach | @frafl Ah, I see that I had the definition of k-tree slightly wrong. Thanks for that! | |
| Apr 7, 2013 at 13:37 | answer | added | fidbc | timeline score: 2 | |
| Apr 7, 2013 at 12:39 | history | edited | Varaquilex | CC BY-SA 3.0 |
deleted 40 characters in body
|
| Apr 7, 2013 at 12:33 | history | edited | Varaquilex | CC BY-SA 3.0 |
added 902 characters in body
|
| Apr 7, 2013 at 12:32 | comment | added | Varaquilex | @fidbc The input is given to me about how to build the graph. Please see the latest edit in the post. | |
| Apr 7, 2013 at 12:31 | comment | added | Raphael | @fidbc: I think you should make an answer out of the first part of your latest comment. Volkan does not imply randomness in any kind, so your example is likely the correct answer. | |
| Apr 7, 2013 at 12:28 | history | edited | Raphael |
edited tags
|
|
| Apr 7, 2013 at 10:11 | comment | added | frafl | @G.Bach: What you define is a $2$-tree, but I forgot that they don't have to be connected. Volkan İlbeyli: My comment was an invitation to look up these terms and see if they match your problem. | |
| Apr 7, 2013 at 9:23 | comment | added | John K. | It can be arbitrarily few, right? You can make arbitrary long paths in three directions. Where the paths have the property that every vertex sees the two vertices closer to the triangle. | |
| Apr 7, 2013 at 3:21 | comment | added | fidbc | It does make a difference. Suppose the enemy chooses the edges and let 1,2,3 be the initial vertices. The enemy can choose to add vertices 4,...,n all of them adjacent to 1 and 2. Therefore the largest cycle/path would have length 4. If the edges are added randomly, its a completely different story. You might have to calculate the expected max length of a cycle/path. Finally, if you get to choose how to add the edges, then you can add them in such a way that the graph is planar and all vertices are in the unbounded face, therefore obtaining a Hamiltonian graph. | |
| Apr 7, 2013 at 2:34 | comment | added | Varaquilex | What difference will it make? Say, enemy. I don't know what I will get, but whatever I get, my answer should be precise. As I said, it's random how edges are added. The only rule is, every newly added node is connected to the graph by 2 edges. And, as far as I can tell, this does not alter the Hamiltonian property of the graph. | |
| Apr 7, 2013 at 1:55 | history | tweeted | twitter.com/#!/StackCompSci/status/320716467979034624 | ||
| Apr 7, 2013 at 1:06 | comment | added | fidbc | It is not clear if you choose the way to add the new edges at each step or an "enemy" chooses them. Could you please explain this? | |
| Apr 6, 2013 at 23:26 | comment | added | G. Bach | @frafl I think you can also construct a 3-tree using that procedure, if when adding a new vertex you only choose two vertices that are adjacent as the neighborhood of the new vertex. | |
| Apr 6, 2013 at 22:48 | history | edited | Varaquilex | CC BY-SA 3.0 |
tags added
|
| Apr 6, 2013 at 22:42 | comment | added | Varaquilex | I'm exactly searching for the largest number of nodes, which satisfy the following: I will start from a node, traverse as much nodes as possible exactly once, and come back to where I started. I don't know it this fits what you described. | |
| Apr 6, 2013 at 22:39 | review | First posts | |||
| Apr 6, 2013 at 23:04 | |||||
| Apr 6, 2013 at 22:36 | comment | added | frafl | Your are searching for a largest cycle in a 2-tree with $N\geq 3$ vertices? | |
| Apr 6, 2013 at 22:34 | history | edited | Varaquilex |
edited tags
|
|
| Apr 6, 2013 at 22:20 | history | asked | Varaquilex | CC BY-SA 3.0 |