← All problems

Circulant graph conjecture for monophonic position number two

5 years old · traced to

Let nn be an integer, and let a circulant graph mean a graph whose vertices are arranged cyclically with adjacency determined by a fixed set of cyclic differences. The monophonic position number is denoted by aa, and the diameter by DD. Circulant graph conjecture. For any n≥11n\geq 11, there is a circulant graph with order nn, monophonic position number a=2a=2, and diameter D=2D=2. The preceding theorem establishes existence of some graph with these parameters if and only if n∈{3,4,5,8}n\in\{3,4,5,8\} or n≥11n\geq 11; the conjecture strengthens the large-order existence assertion by requiring the graph to be circulant, based on computational evidence.

References
  1. James Tuite, Elias John Thomas and Ullas Chandran S. V., “On some extremal position problems for graphs”, arXiv:2106.06827 (2022).

Progress summary

Refreshed
Open · progress reported

A submitted argument claims the universal existence statement fails at order fifteen, but that counterexample has not been independently checked.

Tuite, Thomas, and Chandran formulate the conjecture that every order n≥11n\geq 11 has a circulant graph with monophonic position number 22 and diameter 22.

Known results

  • Tuite, Thomas, and Chandran (2021): some graph with these parameters exists exactly for n∈{3,4,5,8}n\in\{3,4,5,8\} or n≥11n\geq 11; the circulant strengthening remains conjectural.

November 7, 2026 claimed counterexample

A submitted proof argues that no diameter-22 circulant graph of order 1515 has monophonic position number 22: each such graph allegedly contains a triangle, or is the exceptional graph C5[3K1]C_5[3K_1], and either configuration supplies a triple that is an mp-set. If correct, this refutes the conjecture; the argument is unverified.

Current status (as of November 2026): The conjecture is open in the published record, while an unverified submission claims a counterexample at n=15n=15.

Sources

Solutions 1

No order-15 circulant has diameter 2 and monophonic position number 2See full solutionHide full solution

Result and scope. Tuite-Thomas-Chandran (arXiv:2106.06827v3; Ars Math. Contemp. 2025) Conjecture 4.5 asserts that for every n >= 11 there is a circulant graph of order n with diameter 2 and monophonic position number 2 (still listed as open in the survey arXiv:2501.19385 v5, August 2026). False at the interior order 15. Every diameter-2 circulant of order 15 contains a triangle, or is C5[3K1] (jumps {1,4,6} or {2,3,7}) with three open twins; both kinds of triple are mp-sets. Verified circulant examples exist at every other order 11..40 (supplementary; not claimed beyond).

Complete proof: No order-15 circulant has diameter 2 and monophonic position number 2 · PDF.

The paper page contains the supplementary proof-source JSON and extract_sources.py. The linked paper supplies the complete argument and states the precise scope of the Lean certificate, ordinary proofs, supporting computations, and source interpretation. Those qualifications are retained here; a supporting computation is not a proof of a broader statement.

This is an AI-assisted research preprint. Internal review is not external journal peer review. Bounded prior-art searches do not establish worldwide priority. See the paper for formalization and trust limits.