Genetic theory for cubic graphs

Abstract

We partition the set of unlabelled cubic graphs into two disjoint sets, namely “genes” and “descendants”, where the distinction lies in the absence or presence, respectively, of special edge cutsets. We introduce three special operations called breeding operations which accept, as input, two graphs, and output a new graph. The new graph inherits most of the structure of both the input graphs, and so we refer to the input graphs as parents and the output graph as a child. We also introduce three more operations called parthenogenic operations which accept a single descendant as input, and output a slightly more complicated descendant. We prove that every descendant can be constructed from a family of genes via the use of our six operations, and state the result that this family is unique for any given descendant.