Prime-distance characterization of circulant graphs

About 5 years old · traced to

For integers nn and kk with k≤n/2k\leq n/2, let Circ⁡(n,k)\operatorname{Circ}(n,k) denote the circulant graph with these parameters. A graph is a prime distance graph if its vertices can be labeled by distinct integers so that adjacent vertices receive labels whose absolute difference is prime. Prime-distance circulant conjecture. The circulant graph Circ⁡(n,k)\operatorname{Circ}(n,k) is a prime distance graph if and only if none of the following hold:

  1. nn is odd and k=2k=2.
  2. nn is odd and k=(n−1)/2k=(n-1)/2.
  3. (n,k)=(6,2)(n,k)=(6,2).

The claim extends the preceding classification theorem to the remaining parameter values; it was verified in the source for n≤14n\leq 14, but is otherwise open.

References

Primary source

Joshua D. Laison, Colin Starr and Andrea Walker, “Finite Prime Distance Graphs and 2-Odd Graphs”, arXiv:2106.02177 (2021).

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.