Circulant graph conjecture for monophonic position number two
Let 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 , and the diameter by . Circulant graph conjecture. For any , there is a circulant graph with order , monophonic position number , and diameter . The preceding theorem establishes existence of some graph with these parameters if and only if or ; the conjecture strengthens the large-order existence assertion by requiring the graph to be circulant, based on computational evidence.
References
- James Tuite, Elias John Thomas and Ullas Chandran S. V., “On some extremal position problems for graphs”, arXiv:2106.06827 (2022).
Progress summary
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 has a circulant graph with monophonic position number and diameter .
Known results
- Tuite, Thomas, and Chandran (2021): some graph with these parameters exists exactly for or ; the circulant strengthening remains conjectural.
November 7, 2026 claimed counterexample
A submitted proof argues that no diameter- circulant graph of order has monophonic position number : each such graph allegedly contains a triangle, or is the exceptional graph , 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 .
Sources
Solutions 1
No order-15 circulant has diameter 2 and monophonic position number 2See 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.