There Are No Cubic Graphs on 26 Vertices with Crossing Number 10 or 11
- PDF / 363,302 Bytes
- 9 Pages / 439.37 x 666.142 pts Page_size
- 67 Downloads / 176 Views
(0123456789().,-volV)(0123456789().,-volV)
ORIGINAL PAPER
There Are No Cubic Graphs on 26 Vertices with Crossing Number 10 or 11 Kieran Clancy1 • Michael Haythorpe1 Ed Pegg Jr2
•
Alex Newcombe1
•
Received: 23 September 2019 / Revised: 12 May 2020 Ó Springer Japan KK, part of Springer Nature 2020
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. Keywords Crossing number Cubic graphs Conjecture QuickCross heuristic Coxeter graph Levi graph Tutte–Coxeter graph
1 Introduction In this manuscript we restrict our consideration to simple, undirected, connected graphs. Such a graph G has the vertex set V(G) and edge set EðGÞ fu; vg j u; v 2 VðGÞ . A drawing, is a representation of a graph in the & Michael Haythorpe [email protected] Kieran Clancy [email protected] Alex Newcombe [email protected] Ed Pegg Jr [email protected] 1
Flinders University, 1284 South Road, Tonsley 5042, Australia
2
Wolfram Research, 100 Trade Centre Drive, Champaign, IL 61820, USA
123
Graphs and Combinatorics
plane, with vertices represented as distinct points and edges as continuous arcs connecting the points associated to vertices. An arc representing the edge fu; vg begins and ends at the points associated with u and v respectively and in such a way that the interior of the arc does not contain any points associated with vertices. We shall refer to the points and arcs given by a drawing as the ‘vertices’ and ‘edges’ of the drawing. If a graph can be drawn so that the edges of the drawing only intersect other edges at a common vertex, then it is a planar graph. Henceforth, we will take a crossing between two edges to describe an intersection between the interiors of the edges. Unquestionably, the seminal result in planarity is Kuratowski’s theorem, which states that a graph is planar if and only if it contains neither a subdivision of K5 nor of K3;3 [12]. If a graph is non-planar, then one may ask how close it is to being planar. One such measure is the crossing number. For any given drawing of a non-planar graph, there will be a positive number of crossings. Then the crossing number is the minimum number of crossings over all valid drawings of that graph. The crossing number of graph G is denoted cr(G). For example, Fig. 1 displays the Petersen graph [9] drawn in two different ways. The first, standard, drawing has five crossings. However, the second drawing has only two, which is known to be the minimum possibl
Data Loading...
