Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
3  
in the fifth talk in this list it is conjectured order $\log(n)\log(n−1)\dots \log(2)$ facstaff.unca.edu/pbahls/GGGstuff/2008/… –  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

1 Answer 1

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|improve this answer
    
by the same author: oeis.org/A006967 –  Pietro Majer May 31 '11 at 12:33

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.