MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

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

How can one count the number of graceful labelings of a path graph?

share|cite|improve this question
in the fifth talk in this list it is conjectured order $\log(n)\log(n−1)\dots \log(2)$… – Pietro Majer May 31 '11 at 8:44
Nice, thanks. I guess I had thought there would be a closed formula! – Dr Shello Jun 2 '11 at 0:43

An efficient algorithm is described in a paper by Michael Adamaszek which is powerful enough to count the number of graceful labelings of paths up to length 40. It concludes: "It also remains an open question to find an exponential upper bound on [the number of graceful labelings of paths of length n]"

share|cite|improve this answer
by the same author: – Pietro Majer May 31 '11 at 12:33

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.