Conjecture for minimum coprime numbers of joins of paths

Let PmP_m and PnP_n be paths on m+1m+1 and n+1n+1 vertices, respectively, and let Pm+PnP_m+P_n denote their graph join. The minimum coprime number pr(G)\mathfrak{pr}(G) is the least MM for which the vertices of GG have distinct labels from 1,,M1,\ldots,M such that adjacent labels are relatively prime. The path-join conjecture. For positive integers m,nm,n with mnm\geq n,

pr(Pm+Pn)=m+2n2+1(1)m2.\mathfrak{pr}(P_m+P_n)=m+2n-2+\frac{1-(-1)^m}{2}.

This strengthens the preceding bounded-parameter conjectural upper bound and would determine the minimum coprime number for every join of two paths. The source does not provide a resolution.

Sources & referencesView supporting material

Primary source

John Asplund and N. Bradley Fox, “Minimum Coprime Labelings for Operations on Graphs”, arXiv:1707.04471 (2017).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.