2
$\begingroup$

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

Improve this question
$\endgroup$
2
  • 3
    $\begingroup$ 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/… $\endgroup$
    – Pietro Majer
    Commented May 31, 2011 at 8:44
  • $\begingroup$ Nice, thanks. I guess I had thought there would be a closed formula! $\endgroup$
    – Dr Shello
    Commented Jun 2, 2011 at 0:43

1 Answer 1

Reset to default
2
$\begingroup$

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

Improve this answer
$\endgroup$
1

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .