Does anyone know whether bipartite symmetric graphs are hamiltonian? I'm not sure whether anyone have proved it before, but a nonhamiltonian symmetric bipartite graph would lead to a counterexample to the Lovasz conjecture. I would appreciate any references or ideas.
$\begingroup$
$\endgroup$
10
asked Jul 15, 2018 at 7:23
-
1$\begingroup$ What do you mean by symmetric? $\endgroup$– Ivan IzmestievCommented Jul 15, 2018 at 8:27
-
$\begingroup$ A symmetric graph is a graph that is both edge- and vertex-transitive. $\endgroup$– LeechLatticeCommented Jul 15, 2018 at 10:11
-
1$\begingroup$ Why can't it be bipartite? The cube is both symmetric and bipartite. $\endgroup$– LeechLatticeCommented Jul 15, 2018 at 10:53
-
4$\begingroup$ 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. $\endgroup$– Gordon RoyleCommented Jul 15, 2018 at 11:14
-
1$\begingroup$ 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. $\endgroup$– MikeCommented Jul 23, 2018 at 2:51
|
Show 5 more comments