Result and proof credited to @JesterInABarrel. The proof was publicly shared in a ChatGPT conversation on November 18, 2026 and contributed to this repository with permission. Cinna Davis is not the discoverer or author. This note independently checks and presents the argument.
Original conjecture: Ermelinda DeLaViña, Written on the Wall II, Graffiti.pc Conjecture 318, announced March 4, 2007, listed open in the November 5, 2026 catalogue.
Definitions
All graphs here are finite and simple. The complement has as edges the nonedges of . For a vertex of a connected graph, counts vertices at even distance from , including itself (distance zero).
A set is a total dominating set if every vertex, including those in , has a neighbor in . It is minimal if no proper subset is total dominating. A graph is well total dominated if every inclusion-minimal total dominating set has minimum cardinality.
Conjecture 318. If is connected of order at least two, and
then is well total dominated.
Stronger theorem and proof
Theorem. Under the conjecture's hypotheses, every total dominating set contains a total dominating set consisting of two adjacent vertices. Hence every inclusion-minimal total dominating set has exactly two vertices and .
Proof. Put . Choose for which . Let be the number of nonneighbors of , and the number of missing edges with neither endpoint . Then .
Every vertex other than at even distance from has distance at least two, so it is a nonneighbor of . The vertex itself contributes at most one more vertex:
It follows that . Thus the graph induced by has at most one missing edge.
Partition into independent parts. If a missing edge exists, its two endpoints make one part. All other parts are singletons. Distinct parts are completely adjacent to one another.
Take any total dominating set . The vertex must have a neighbor ; let denote the part containing .
- Suppose meets another part at . Then totally dominates : dominate each other; dominates and every vertex in every other part; and dominates every vertex in .
- Otherwise . Since contains no edges, every vertex of can be dominated by only via . Therefore and is adjacent to all of . The pair totally dominates: dominate each other, dominates , and dominates all other parts.
Every total dominating set therefore contains a total dominating pair. No singleton can totally dominate a simple graph, since its selected vertex has no loop. Every minimal total dominating set consequently has size two. This proves Conjecture 318.
Sharpness of the hypothesis
Let . A universal vertex is joined to four other vertices ; the only edges among those four are and .
The four cross-pair nonedges give . Each of has even distance to itself and the two endpoints of the opposite edge (at distance two via ); has even distance only to itself. Thus
The pair totally dominates, so . The four-element set also totally dominates, and is minimal: removing any endpoint leaves its partner undominated within the set. Hence this graph is not well total dominated. Replacing by would make the conjecture false.
Verification and scope
Run python3 results/graffiti-pc-318/verify.py from the repository root. It enumerates all labeled simple graphs on 2–7 vertices with at most missing edges, computes distances and total domination directly, and checks the stronger theorem on every qualifying connected graph. This covers all graphs of these orders that could satisfy the hypothesis (because forces ). The extra missing-edge layer covers the one-unit relaxation. A total of 419,235 graphs are examined, with 7,337 satisfying the original hypothesis; all pass. The explicit sharpness graph is checked separately.
The finite test is not a substitute for the all-order proof, and no Lean formalization or peer review is claimed. An open catalogue status is not proof of absolute historical priority.