Peter: Thanks for the comment. I am relatively new to mathoverflow. Which of the following ways are considered acceptable in this case: (a) posting an entire new question including a link to this one, (b) posting the new question as a comment on the original question, or (c) commenting under Noam's answer? I thought the purpose of having websites like mathoverflow is to facilitate the discussions on interesting math problems. But if there are certain community policies users should stick to, I would be happy to learn about them.

Thanks for the quick answer! I checked the the next interesting case (36 balls) on hydra.nat.uni-magdeburg.de/packing/cci. And somewhat surprisingly the best known radius beats the 37 ball case.

There is an elegant conjecture posed by Triesch (see: citeseerx.ist.psu.edu/viewdoc/…). It seems that your problem is a special case of it (when the smaller graph is G_{n,d}).