Exploring New Graphs

We are now officially halfway through to the end of the project!

Construction Of The New Graph

Last week, I left off in favor of a more theoretical approach, and would like to introduce one of the graphs I found. In Belcastro’s paper “Families of Dot-Product Snarks on Orientable Surfaces of Low Genus,” two families of snarks are introduced. These are B1HP and B1VP, and are formed from the different choices (horizontally or vertically) of dotting Blanusa-1 with the Petersen graph. The smallest two graphs of each family are shown below.

 At this point, I was motivated to consider a “combination” of these two families by having the Petersen graphs be dotted on in both the vertical and horizontal directions. However, there were a few issues from naively putting the two graphs together, which is shown below. In order to respect the topology of the torus that the graphs are embedded on, we obtain four edge crossings, which are circled in red. These are bad.

 To fix this, I first tried using a different embedding of the graphs. By a result in the paper, this should an isomorphic graph with different embedding. This yields the graph below, which has only one edge crossing.

  To fix this crossing and maintain the cubic property of the graph, I constructed a connector that resulted in the final result.  

Although I still have to test if this still a snark, I now have a more general method of systematically constructing larger and larger graphs for examination.

Other Strategies

One method of proof I have yet to see regarding this problem is a probabilistic method. The gist of this method would be to prove that there exists a non-zero probability that a graph exists or does not exist with a given condition, and it may avoid explicitly constructing a counterexample. While I am not sure whether this method will play nicely with embedding problems, I figure it’s worth a shot learning more about the approach and giving it a try.

Citations

1. Belcastro, Sm., Kaminski, J. Families Of Dot-Product Snarks On Orientable Surfaces Of Low Genus. Graphs And Combinatorics 23, 229–240 (2007). Https://Doi.Org/10.1007/S00373-007-0729-9