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
    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

1

I don't know if I have understand you correctly, but I would say there is at least an exponential lower bound. Consider the following Graph $G$ with $n$ vertices and $m=n/2-1$ orange edges.

Graph

There is a Hamiltonian cycle in $G$ that avoids all the orange edges. Let $S$ be a set of $m/2$ of the orange edges, and let $G_S$ be the graph $G$ with deleted edges $S$. We define by $\Gamma$ the set of all such graphs $G_S$. Deleting an orange edge turns two degree-4 vertices into degree-3 vertices, independently of other deleted edges. Thus the degree sequence for all graphs in $\Gamma$ is the same.

Let us now bound the number of graphs in $\Gamma$. We have ${m \choose m/2}=\Theta(2^m)$ different ways to select $S$. This yields a bound of $\Omega(\sqrt{2}^n)$ for the number of different Hamiltonian graphs with the same degree sequence. Notice that every isometry class of $\Gamma$ has only constant size.