Graffiti.pc Conjecture 318: proof and sharpness

What Lean checks

The all-order theorem uses actual graph distances and undirected complement-edge counts. Every total dominating set contains an adjacent total dominating pair; every minimal set has size two. The stated five-vertex graph proves sharpness of a one-unit relaxation.

Result and proof credited to @JesterInABarrel. This is an external contribution.

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 G¯\overline G has as edges the nonedges of GG. For a vertex vv of a connected graph, disteven(v)\mathop{\mathrm{dist}}_{even}(v) counts vertices at even distance from vv, including vv itself (distance zero).

A set D⊆V(G)D\subseteq V(G) is a total dominating set if every vertex, including those in DD, has a neighbor in DD. 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 GG is connected of order at least two, and

maxvdisteven(v)≥|E(G¯)|,\max_v \mathop{\mathrm{dist}}_{even}(v)\geq |E(\overline G)|,

then GG 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 γt(G)=2\gamma_t(G)=2.

Proof. Put q=|E(G¯)|q=|E(\overline G)|. Choose vv for which disteven(v)≥q\mathop{\mathrm{dist}}_{even}(v)\ge q. Let rr be the number of nonneighbors of vv, and ss the number of missing edges with neither endpoint vv. Then q=r+sq=r+s.

Every vertex other than vv at even distance from vv has distance at least two, so it is a nonneighbor of vv. The vertex vv itself contributes at most one more vertex:

q≤disteven(v)≤r+1.q\leq \mathop{\mathrm{dist}}_{even}(v)\leq r+1.

It follows that s≤1s\leq1. Thus the graph induced by V(G)\{v}V(G)\setminus\{v\} has at most one missing edge.

Partition V(G)\{v}V(G)\setminus\{v\} 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 DD. The vertex vv must have a neighbor a∈Da\in D; let AA denote the part containing aa.

  1. Suppose DD meets another part at bb. Then {a,b}\{a,b\} totally dominates GG: a,ba,b dominate each other; aa dominates vv and every vertex in every other part; and bb dominates every vertex in AA.
  2. Otherwise D⊆A∪{v}D\subseteq A\cup\{v\}. Since AA contains no edges, every vertex of AA can be dominated by DD only via vv. Therefore v∈Dv\in D and vv is adjacent to all of AA. The pair {a,v}\{a,v\} totally dominates: a,va,v dominate each other, vv dominates AA, and aa 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. ▫\square

Sharpness of the hypothesis

Let G=K1∨(2K2)G=K_1\vee(2K_2). A universal vertex zz is joined to four other vertices a,b,c,da,b,c,d; the only edges among those four are abab and cdcd.

The four cross-pair nonedges give q=4q=4. Each of a,b,c,da,b,c,d has even distance to itself and the two endpoints of the opposite edge (at distance two via zz); zz has even distance only to itself. Thus

maxvdisteven(v)=3=q−1.\max_v\mathop{\mathrm{dist}}_{even}(v)=3=q-1.

The pair {z,a}\{z,a\} totally dominates, so γt(G)=2\gamma_t(G)=2. The four-element set {a,b,c,d}\{a,b,c,d\} 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 maxvdisteven(v)≥q\max_v\mathop{\mathrm{dist}}_{even}(v)\ge q by ≥q−1\ge q-1 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 n+1n+1 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 disteven(v)≤n\mathop{\mathrm{dist}}_{even}(v)\le n forces q≤nq\le n). 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.