There Are No Cubic Graphs on 26 Vertices with Crossing Number 10 or 11

Kieran Clancy, Michael Haythorpe, Alex Newcombe, Ed Pegg

Research output: Contribution to journalArticlepeer-review

Abstract

We show that no cubic graphs of order 26 have crossing number larger than 9, which proves a conjecture of Ed Pegg Jr and Geoffrey Exoo that the smallest cubic graphs with crossing number 11 have 28 vertices. This result is achieved by first eliminating all girth 3 graphs from consideration, and then using the recently developed QuickCross heuristic to find drawings with few crossings for each remaining graph. We provide a minimal example of a cubic graph on 28 vertices with crossing number 10, and also exhibit for the first time a cubic graph on 30 vertices with crossing number 12, which we conjecture is minimal.

Original languageEnglish
Pages (from-to)1713-1721
Number of pages9
JournalGraphs and Combinatorics
Volume36
Issue number6
Early online date28 Jun 2020
DOIs
Publication statusPublished - Nov 2020

Keywords

  • Conjecture
  • Coxeter graph
  • Crossing number
  • Cubic graphs
  • Levi graph
  • QuickCross heuristic
  • Tutte–Coxeter graph

Fingerprint Dive into the research topics of 'There Are No Cubic Graphs on 26 Vertices with Crossing Number 10 or 11'. Together they form a unique fingerprint.

Cite this