2
$\begingroup$

There definitely are traceable graphs (hamiltonian-path graph) that have equal number of vertexes and have equal degree information - for example, graph A has vertex A that has degree of three, vertex B degree of four, C degree of three and graph B has vertex A' that has degree of three, vertex B' degree of four, C' degree of three and so forth.

So, what would be the number of distinct traceable graphs that would be like as above?

Or the bound of the number would also be fine.

  • 0
    I suspect that the problem, given a graphical sequence, find (or bound) the number of non-isomorphic graphs with that degree sequence, is hard enough even without the restriction to Hamiltonian graphs.2012-07-08
  • 0
    @GerryMyerson Is there any bound, then? like big-O bound, or, whatever.2012-07-08
  • 0
    Could be. Suggest you look at a special case, to get a feeling for what you're asking. I think there's a theorem that says that if $G$ has $2n-1$ vertices, each of degree $n$, then it's Hamiltonian. The number of non-isomorphic $n$-regular graphs with $2n-1$ vertices is surely tabulated somewhere, probably with estimates on asymptotics.2012-07-08

1 Answers 1