HEXAGONbeta

Counterexamples to five conjectures of Graffiti.pc on domination

A mix of human-written and AI-generated textHuman understanding: some partsmath.CO — Combinatorics

Contributed by Deep Bhattacharjee ↗

Version 1 / Oct 23, 2026 / CC BY 4.0

Abstract

Written on the Wall II, the list of conjectures of the program Graffiti.pc, records Conjectures 319, 352, 358, 359 and 427 as open. We show that all five are false. The counterexamples are caterpillars for Conjectures 352, 358, 359 and 427, and graphs built from complete graphs for Conjecture 319; each comes in an infinite family, and for Conjectures 358, 359 and 427 the difference between the two sides is unbounded.

Provenance statement

Deep Bhattacharjee chose the problem and directed the work. Claude (Anthropic), through Claude Code, carried out the searches and computations, wrote the checking programs and the Lean 4 proofs and drafted the paper. Refutes Graffiti.pc Conjectures 319, 352, 358, 359 and 427. The proofs are written out in the paper; the programs and their outputs are in the release. The author approved the final version. Code and data: release v1.0.1, https://github.com/creelie/eCY/releases/tag/v1.0.1.
AI provenance filesAI-PROVENANCE-HEXAGON.md · 1 KB

Tools used

Anthropic
Claude CodeVersion Opus 5.5 Ultracode

References

  1. S. Bahad r, T. Ekim and D. Gözüpek, Well-totally-dominated graphs , Ars Math. Contemp. 20 (2021), 209--222. 10.26493/1855-3974.2465.571DOI
  2. D. Bhattacharjee, P. Mandal and U. Bhattacharya, Resolving Erdős--Ulam monochromatic union-closed family conjectures , preprint, 2026. arXiv:2610.02833 (https://arxiv.org/abs/2610.02833)arXiv
  3. E. J. Cockayne, R. M. Dawes and S. T. Hedetniemi, Total domination in graphs , Networks 10 (1980), 211--219. 10.1002/net.3230100304DOI
  4. E. DeLaViña, Graffiti.pc: a variant of Graffiti , in: Graphs and Discovery, DIMACS Ser. Discrete Math. Theoret. Comput. Sci. 69, Amer. Math. Soc., Providence, RI, 2005, 71--79. 10.1090/dimacs/069/05DOI
  5. E. DeLaViña, Written on the Wall II (conjectures of Graffiti.pc) , http://cms.uhd.edu/faculty/delavinae/research/wowII/; version of 26 July 2026 archived at https://web.archive.org/web/20260726061534/http://cms.uhd.edu/faculty/delavinae/research/wowII/all.htmllink
  6. E. DeLaViña, C. E. Larson, R. Pepper and B. Waller, Graffiti.pc on the total domination number of a tree , Congr. Numer. 195 (2009), 5--18.
  7. E. DeLaViña, Q. Liu, R. Pepper, B. Waller and D. B. West, Some conjectures of Graffiti.pc on total domination , Congr. Numer. 185 (2007), 81--95.
  8. W. J. Desormeaux and M. A. Henning, Lower bounds on the total domination number of a graph , J. Comb. Optim. 31 (2016), 52--66. 10.1007/s10878-014-9708-2DOI
  9. S. Fajtlowicz, On conjectures of Graffiti , Discrete Math. 72 (1988), 113--118. 10.1016/0012-365X(88)90199-9DOI
  10. M. A. Henning and A. Yeo, Total Domination in Graphs , Springer Monographs in Mathematics, Springer, New York, 2013. 10.1007/978-1-4614-6525-6DOI
Show all 13 referencesShow fewer references
  1. C. Jordan, Sur les assemblages de lignes , J. Reine Angew. Math. 70 (1869), 185--190. 10.1515/crll.1869.70.185DOI
  2. B. D. McKay and A. Piperno, Practical graph isomorphism, II , J. Symbolic Comput. 60 (2014), 94--112. 10.1016/j.jsc.2013.09.003DOI
  3. R. A. Wright, B. Richmond, A. Odlyzko and B. D. McKay, Constant time generation of free trees , SIAM J. Comput. 15 (1986), 540--548. 10.1137/0215039DOI

Version history

  1. v1Submitted by Deep BhattacharjeeInitial depositCurrentOct 23, 2026