Wikipedia:Reference desk/Archives/Mathematics/2013 December 13

Mathematics desk
< December 12 << Nov | December | Jan >> December 14 >
Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.


December 13

edit

Number of Hamiltonian paths question

edit

Assume a graph with N vertices and 3*N undirected edges. As N grows large, what is the general configuration of the graph that has the most Hamiltonian paths and what is the general configuration of the graph that has the least non-zero Hamiltonian paths? (And no this isn't homework, this is off of musings on how an Alternate History would have US State boundaries better organized to give more Hamiltonian paths among the states, but in my question above, the graph doesn't have to be Planar).Naraht (talk) 22:52, 13 December 2013 (UTC)[reply]

Just split California in half --DHeyward (talk) 03:22, 14 December 2013 (UTC)[reply]
Why would splitting California in half be more effective in increasing the number of Hamiltonian paths than say Tennessee?Naraht (talk) 05:39, 15 December 2013 (UTC)[reply]