5 papers
Constructing Families of Cospectral Regular Graphs
Michael Haythorpe, Alex Newcombe
A set of graphs are called cospectral if their adjacency matrices have the same characteristic polynomial. In this paper we introduce a simple method for constructing infinite fami…
The maximum crossing number of
Michael Haythorpe, Alex Newcombe
We determine that the maximum crossing number of is 78, which closes the previously best known range of between 68 and 80. The proof uses several techniques which…
On the Crossing Number of the Cartesian Product of a Sunlet Graph and a Star Graph
Michael Haythorpe, Alex Newcombe
The exact crossing number is only known for a small number of families of graphs. Many of the families for which crossing numbers have been determined correspond to cartesian produ…
There are no Cubic Graphs on 26 Vertices with Crossing Number 10 or 11
Kieran Clancy, Michael Haythorpe, Alex Newcombe +1
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…
An effective crossing minimisation heuristic based on star insertion
Kieran Clancy, Michael Haythorpe, Alex Newcombe
We present a new heuristic method for minimising crossings in a graph. The method is based upon repeatedly solving the so-called {\em star insertion problem} in the setting where t…