Timeline for Reference request: Bipartite symmetric graphs are hamiltonian
Current License: CC BY-SA 4.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 5, 2018 at 11:36 | comment | added | Peter Heinig | I believe this is an open question. A decade-old yet still helpful related source is 'Annelies Heus: A study of necessary and sufficient conditions for vertex transitive graphs to be Hamiltonian. University of Amsterdam 2008'. The question is not answered there, needless to say. | |
| Jul 23, 2018 at 2:51 | comment | added | Mike | This may or may not be a triviality but I assume you mean Hamiltonian cycle in each connected component or that the graph is connected. i.e., not a vertex-disjoint collection of cycles all of the same size. | |
| Jul 15, 2018 at 11:26 | comment | added | Gordon Royle | Not quite, but things like Cayley graphs of certain groups, or transitive graphs of certain orders (products of few primes). Look up the work of Dave Witte (aka Dave Morris) and Joy Morris. | |
| Jul 15, 2018 at 11:17 | comment | added | LeechLattice | So are there any examples where some kind of graph symmetry implies hamiltonicity? | |
| Jul 15, 2018 at 11:14 | comment | added | Gordon Royle | As far as I know, nothing substantive about the question of whether vertex-transitive graphs have Hamilton cycles (other than the handful of known non Hamiltonian examples) has recently been proved. There has been some progress on gradually increasing the number of families of transitive graphs known to be Hamiltonian, but far short of extending to either bipartite or symmetric (or both) graphs. | |
| Jul 15, 2018 at 10:54 | comment | added | Ivan Izmestiev | You are right, sorry. | |
| Jul 15, 2018 at 10:53 | comment | added | LeechLattice | Why can't it be bipartite? The cube is both symmetric and bipartite. | |
| Jul 15, 2018 at 10:25 | comment | added | Ivan Izmestiev | But then it cannot be bipartite. | |
| Jul 15, 2018 at 10:11 | comment | added | LeechLattice | A symmetric graph is a graph that is both edge- and vertex-transitive. | |
| Jul 15, 2018 at 8:27 | comment | added | Ivan Izmestiev | What do you mean by symmetric? | |
| Jul 15, 2018 at 7:23 | history | asked | LeechLattice | CC BY-SA 4.0 |