math.CO — Combinatorics
Counterexamples, Spectral Obstructions, and Deletion Stability for WOW-284
WOW-284 is a Graffiti conjecture asserting that every connected graph of order at least three and girth at least five has minimum dual degree at most , where is the distance matrix and the dual degree of a vertex is the average degree of its neighbors. We refute it with exact counterexamples on , , , and vertices and study the structure of regular counterexamples. For a connected -regular graph of girth at least five and diameter three, we prove that , the maximum being over the nonprincipal adjacency eigenvalues, so strict failure is a spectral window condition. The closed window alone, without any diameter assumption, forces when , and an integral excess matrix derived from the optimal polynomial sharpens this bound for diameter-three counterexamples. Every regular strict counterexample has degree at least six and diameter at most four, and in degree six it has at most vertices. Under vertex deletion, the Hoffman-Singleton graph remains a strict counterexample after the removal of any five vertices, while an explicit six-vertex deletion destroys strictness. A degree- Moore graph, if one exists, remains a connected strict counterexample after the removal of any vertices. Every strict counterexample has at least vertices, and an exhaustive search excludes orders up to . The strict induced subgraphs of the Hoffman-Singleton graph of orders to are classified up to automorphism; among them are three further irregular counterexamples of order .