Does a prime labeling exist for all caterpillars, which are trees with every vertex being at most distance 1 from a central path? By a prime labeling, we mean a way to label the n vertices with the integers 1 to n such that each pair of adjacent vertices is relatively prime.

Gallian's survey paper on graph labelings claims one exists and cites Fu and Huang's "On prime labelling," which in turn cites an unpublished paper for this result. Does anyone know if caterpillars have been proven to be prime and how this labeling is constructed?

  • $\begingroup$ What does a "prime labeling" mean in this context? $\endgroup$ – Henning Makholm Nov 15 '17 at 22:00
  • $\begingroup$ I believe it's a bijective labeling of the vertices $1$ through $n$ where every pair of adjacent vertices is coprime. I did a little searching and it appears the paper isn't actually unpublished, but rather published in a Malaysian journal in 1988 and not available online. $\endgroup$ – NoName Nov 16 '17 at 1:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.