Extremal Counterexamples and Structural Rigidity for Graffiti.pc Conjecture 138
A conjecture of Graffiti.pc relates the largest induced path to the separation of maximum-degree vertices in a graph square. We construct counterexamples at every order fromten onwards, establish sharp replacement inequalities, and give exact finite certificates forminimum-order classifications in connected graphs and trees. The minimum counterexamplesfor square-graph distance are two explicitly described six-cycle blow-ups. Earlier reportedcounterexamples are distinguished from the extremal results developed here.
Authors
- Tony Newton (ORCID: https://orcid.org/0009-0009-9189-6431)
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-11-18
- DOI
- https://doi.org/10.5281/zenodo.24354328
- Primary Topic
- Advanced Graph Theory Research
- Type
- preprint