Timeline for What is the smallest uniquely hamiltonian graph with minimum degree at least 3?
Current License: CC BY-SA 4.0
16 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 26, 2023 at 6:10 | history | edited | Gordon Royle | CC BY-SA 4.0 |
Added explanation of the graph
|
| Oct 17, 2020 at 13:59 | history | edited | Tony Huynh | CC BY-SA 4.0 |
deleted 5 characters in body; edited tags
|
| Jan 11, 2017 at 8:13 | vote | accept | Gordon Royle | ||
| Jan 11, 2017 at 5:09 | answer | added | Gordon Royle | timeline score: 10 | |
| Nov 29, 2016 at 5:35 | comment | added | Gordon Royle | @PeterTaylor The Barefoot/Entringer paper (which I can only see if I actually walk to the library, which I have not yet done) is concerned with u.h. graphs with $n^2/4+1$ edges. The 2 such graphs on 10 vertices each have two vertices of degree 2 and I believe this pattern continues. | |
| Nov 29, 2016 at 5:18 | comment | added | Gordon Royle | @MartinRubey It is easy to generate the 10-vertex graphs (maybe 3-4 seconds), a few thousand times slower to check them for unique hamilton cycles, but overall an easy computation. | |
| Nov 28, 2016 at 15:59 | comment | added | Peter Taylor | If you have access to it, A census of maximum uniquely hamiltonian graphs by Barefoot and Entringer claims in the abstract to provide an algorithm for constructing maximal uniquely Hamiltonian graphs of order $n$. | |
| Nov 28, 2016 at 14:17 | comment | added | Martin Rubey | According to A004108 (Number of n-node unlabeled connected graphs without endpoints) there are "only" 9808209 graphs to check on 10 vertices. Might it be possible to generate these efficiently, and then check for a unique hamiltonian cycle? | |
| Nov 28, 2016 at 12:34 | comment | added | Gordon Royle | Aha, figured it out. The 10-vertex graph in the aforementioned paper has the property that it has an edge that is contained in only one hamilton cycle. This means it can be turned into a uniquely hamiltonian graph via a simple doubling procedure. So while the 10-vertex graph itself is not uniquely hamiltonian, it leads to a 20-vertex example that is. | |
| Nov 28, 2016 at 12:05 | comment | added | Gordon Royle | @Wolfgang This is a very strange paper. I agree that it claims that there is such a graph on 10 vertices. However it does not actually contain any graphs, except for a diagram (Figure 1) of a 10-vertex graph that is not uniquely hamiltonian. The paper spends almost all its time on an extended description of a search algorithm that judging by the number of acronyms used must be quite complicated, and plenty of tables of running times and success rates etc. But no uniquely hamiltonian graphs :-( | |
| Nov 28, 2016 at 11:54 | history | edited | András Bátkai |
added arxiv tag
|
|
| Nov 28, 2016 at 11:10 | comment | added | Wolfgang | A google search brings up this article: link.springer.com/chapter/10.1007%2F978-3-319-39636-1_1. And it claims there is such a graph on only 10 vertices. | |
| Nov 28, 2016 at 9:52 | answer | added | Tony Huynh | timeline score: 9 | |
| Nov 28, 2016 at 9:24 | comment | added | Gordon Royle | The numbers are just an arbitrary labelling so no further information there. | |
| Nov 28, 2016 at 9:18 | comment | added | Ilya Bogdanov | What are the numbers placed for? They definitely don't indicate the cycle (which is obvious). Do they bear some additional info? | |
| Nov 28, 2016 at 6:36 | history | asked | Gordon Royle | CC BY-SA 3.0 |