A computational attack on the conjectures of Graffiti: New counterexamples and proofs Original Research Article

Graffiti is a computer program that checks for relationships among certain graph invariants. It uses a database of graphs and has generated well over 700 conjectures. Having obtained a readily available computer tape of all the nonisomorphic graphs with 10 or fewer vertices, we have tested approximately 200 of the Graffiti conjectures and have found counterexamples for over 40 of them. For each conjecture that failed we display a counterexample. We also provide results that came from analyzing those conjectures which had a small number of counterexamples. Finally, we prove some results about four of the conjectures.