Progress On Coding And Other Approaches

Coding Progress

Last time I left off writing some code that would determine whether or not a graph has a polyhedral embedding. Currently, I have successfully tested the code for the Petersen snark, so the next step would be testing other graphs. There are many databases online, that I will try to work with in the future.

There are also some other features I want to add to my code. First of all, I want the code to be able to compute the defect of a graph, which is essentially a measure of how “bad” an embedding is. In particular, it is related to the number of edges that appear twice on a facial walk or the number of edges that two different facial walk touch. This metric is important because a snark will have polyhedral embedding if and only if the defect is equal to 0. 

Another feature I want to try an implement is computing the dot product of two graphs. Because the dot product of two snarks is a snark, this operation will help me test a select few graphs with many vertices that are more likely to offer results. In fact, Kochol’s counterexample is constructed from the dot product of three Petersen snarks.

Theoretical Progress

I have been investigating different families of snarks, more specifically those formed from dot products. One family of particular interest is B1HP, formed by dotting the Petersen snark with the Blanusa snark in the horizontal direction. I think it would be interesting to examine different statistics about defects in this family once my code has matured further.

Blanusa-1 snark

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
2. Mohar, Bojan & Steffen, Eckhard & Vodopivec, Andrej. (2008). Relating Embedding And Coloring Properties Of Snarks. ARS MATHEMATICA CONTEMPORANEA. 1. 169-184. 10.26493/1855-3974.49.B88.