There are no cubic graphs on 26 vertices with crossing number 10 or 11

DOI10.1007/S00373-020-02204-6MaRDI QIDQ2657046zbMATH OpenOpenAlexFDO

Authors Kieran Clancy, Michael Haythorpe, Alex Newcombe, Ed jun. Pegg

Publication date 17 March 2021

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1804.10336

zbMATH Keywords

conjectureCoxeter graphcrossing numbercubic graphsLevi graphquickcross heuristicTutte-Coxeter graph

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph representations (geometric and intersection representations, etc.) (05C62)

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 good embeddings of each remaining graph. In the cases where the embedding found has 10 or more crossings, the heuristic is re-run with a different settings of parameters until an embedding with fewer than 10 crossings is found. 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.

Recommendations

• Cubic graphs with crossing number two
• scientific article; zbMATH DE number 881174
• Crossing number is hard for cubic graphs
• Mathematical Foundations of Computer Science 2004
• The minimum of the maximum rectilinear crossing numbers of small cubic graphs

Cites work

• A theorem on tait colorings with an application to the generalized Petersen graphs
• Adding one edge to planar graphs makes crossing number and 1-planarity hard
• An effective crossing minimisation heuristic based on star insertion
• An ILP-based Proof System for the Crossing Number Problem
• Crossing number is hard for cubic graphs
• Crossing Number is NP-Complete
• Crossing numbers of graphs
• Excluded minors in cubic graphs
• Fast generation of regular graphs and construction of cages
• scientific article; zbMATH DE number 5485473 (Why is no real title available?)
• scientific article; zbMATH DE number 227006 (Why is no real title available?)
• scientific article; zbMATH DE number 3097897 (Why is no real title available?)
• My Graph
• New bounds on crossing numbers
• Non-planar core reduction of graphs
• Survey of the crossing number of graphs
• The graph crossing number and its variants: a survey

Cited in

(5)

• Cubic graphs with crossing number two
• scientific article; zbMATH DE number 881174 (Why is no real title available?)
• On non-planarity of cubic graphs
• A systematic approach to crossing numbers of Cartesian products with paths
• A systematic approach to crossing numbers of Cartesian products with paths

Describes a project that uses

Uses Software

• OEIS
• GENREG

This page was built for publication: There are no cubic graphs on 26 vertices with crossing number 10 or 11

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2657046)