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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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. – Gerry Myerson Jul 8 '12 at 3:18
@GerryMyerson Is there any bound, then? like big-O bound, or, whatever. – Schzward Zackers Jul 8 '12 at 3:28
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. – Gerry Myerson Jul 8 '12 at 3:34

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.


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.

share|cite|improve this answer

Your Answer


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.