Simultaneous Euler and Hamiltonian Paths

Probability Level 5

How many homeomorphically distinct graphs exist such that they contain a path that is both Eulerian and Hamiltonian?

Definitions:

  • A walk on a graph is a sequence (v0,e1,v1,e2,v2,,ek,vk)(v_0, e_1, v_1, e_2, v_2, \ldots, e_k, v_k), where v0,v1,,vkv_0, v_1, \ldots, v_k are vertices of the graph, e1,e2,,eke_1, e_2, \ldots, e_k are edges of the graph, and ei={vi1,vi}e_i = \{v_{i-1}, v_i\} for all i=1,2,,ki = 1, 2, \ldots, k.
  • An Eulerian path is a walk that uses each edge exactly once. That is, e1,e2,,eke_1, e_2, \ldots, e_k are all distinct, and they are exactly the edges of the graph in some order.
  • A Hamiltonian path is a walk that uses each vertex exactly once. That is, v0,v1,,vkv_0, v_1, \ldots, v_k are all distinct, and they are exactly the vertices of the graph in some order.
  • A subdivision of an edge e={u,v}e = \{u,v\} in a graph gives a modified version of the graph, having an additional vertex ww and two additional edges {u,w},{v,w}\{u,w\}, \{v,w\}, and missing the original edge ee. A subdivision of a graph is the result of subdividing any number of the edges of the graph. (An edge that's the result of some earlier subdivision may still be subdivided.)
  • Two graphs G,GG, G' are homeomorphic if there is some graph HH that is both isomorphic to a subdivision of GG and isomorphic to a subdivision of GG'. Informally, if GG and GG' are drawn with vertices as invisible points and edges as arcs, then two homeomorphic graphs "look the same." Two graphs are homeomorphically distinct if they are not homeomorphic.
×

Problem Loading...

Note Loading...

Set Loading...