Prime-distance characterization of circulant graphs

From papers

For integers nn and kk with kn/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=(n1)/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 n14n\leq 14, but is otherwise open.

Progress summary

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

Sources & referencesView supporting material

Primary source

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

Solutions 0

No solutions have been posted yet.