Graph Theory » Basic G.T. » Cycles

Every prism over a 3-connected planar graph is hamiltonian. ★★

Author(s): Kaiser; Král; Rosenfeld; Ryjácek; Voss

Conjecture   If $ G $ is a $ 3 $-connected planar graph, then $ G\square K_2 $ has a Hamilton cycle.

Keywords:

Posted by fhavet
updated March 11th, 2013
add new comment
Graph Theory » Directed Graphs

Hoàng-Reed Conjecture ★★★

Author(s): Hoang; Reed

Conjecture   Every digraph in which each vertex has outdegree at least $ k $ contains $ k $ directed cycles $ C_1, \ldots, C_k $ such that $ C_j $ meets $ \cup_{i=1}^{j-1}C_i $ in at most one vertex, $ 2 \leq j \leq k $.

Keywords:

Posted by fhavet
updated March 11th, 2013
add new comment
Graph Theory » Directed Graphs » Tournaments

Edge-disjoint Hamilton cycles in highly strongly connected tournaments. ★★

Author(s): Thomassen

Conjecture   For every $ k\geq 2 $, there is an integer $ f(k) $ so that every strongly $ f(k) $-connected tournament has $ k $ edge-disjoint Hamilton cycles.

Keywords:

Posted by fhavet
updated March 8th, 2013
add new comment
Graph Theory » Directed Graphs

Hamilton cycle in small d-diregular graphs ★★

Author(s): Jackson

An directed graph is $ k $-diregular if every vertex has indegree and outdegree at least $ k $.

Conjecture   For $ d >2 $, every $ d $-diregular oriented graph on at most $ 4d+1 $ vertices has a Hamilton cycle.

Keywords:

Posted by fhavet
updated March 8th, 2013
add new comment