THE MINIMUM GRAOVAC–GHORBANI INDEX OF BICYCLIC GRAPHS: A PROOF OF THE PACHECO–DE LIMA–OLIVEIRA CONJECTURE
Pacheco, de Lima and Oliveira conjectured in 2021 that the minimum Graovac–Ghorbani index among connected bicyclic graphs of order n ≥ 9 is attained uniquely by thetheta graph Θ(2, 2, n − 3) for odd n and by Θ(3, 3, n − 5) for even n. We prove both assertions.The proof combines sharp bounds on individual edge contributions with a classification of edgesthat partition the vertices into two equally large strict distance classes. A compensation argu-ment excludes adjacent twins and pendent vertices. We also derive an explicit edge-imbalanceformula for bipartite graphs consisting of internally disjoint paths with common terminals, ob-tain sharp minima in these families, and establish a positive separation between the bicyclicminimum and every other index value at fixed order.
Authors
- Tony Newton (ORCID: https://orcid.org/0009-0009-9189-6431)
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-11-20
- DOI
- https://doi.org/10.5281/zenodo.24400625
- Primary Topic
- Graph theory and applications
- Type
- preprint