Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Suppose that we set the number of vertexes in a graph (and suppose that in a graph, there is no subgraph separate or isolated from other subgraphs).

Then, there are several ways to connect the vertexes using edges.

Out of those graphs possible, there will be some graphs which have hamiltonian paths (I am not talking of cycles) and graphs that do not have hamiltonian paths.

We know that some graphs can be redrawn without changing edge and vertex information into another graph. (e.g. rotation, reflection etc.)

So, if we count the number of total graphs possible that hamiltonian paths, how many of them will be virtually equal to each other? And how do you get the number?

Also, for graphs that do not have hamiltonian paths, how many of them will be virtually equal to each other? How do you get the number?

share|improve this question

2 Answers 2

up vote 1 down vote accepted

Jargon alert: What you call "virtually identical" graphs are commonly known as isomorphic graphs, so a rephrase of one of your questions might be

How many non-isomorphic graphs on $n$ vertices have Hamiltonian paths?

Now comes the bad news: there's no known general answer to that question. For a specific number of vertices, like 10, there are ways to get the answer, but they are incredibly time-consuming. Sorry 'bout that.

share|improve this answer

If you instead ask for the number of nonisomorphic Hamiltonian graphs (ie. graphs that contain a Hamiltonian cycle) then the sequence in context is the following

http://oeis.org/A003216

Perhaps someone could compute a few terms of the related sequence for graphs with Hamiltonian paths and put it on sloane?

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.