Properties of Cubic Graphs

Cubic graphs are of central importance in graph theory since many graph theoretical problems can be reduced to the case of cubic graphs. The project consists of three parts. Firstly, we will generate new snarks and analyze their properties. Snarks are non-3-edge colorable cyclically 4- edge connected cubic graphs which have girth at least 5. They are of central interest in graph theory since for several famous conjectures a potential counterexample must be a snark. Secondly, we will apply new approaches towards the subsequent conjecture: Dominating Circuit Conjecture (DCC): Every cyclically 4-edge connected cubic graph G has a circuit which contains at least one end-vertex of every edge of G. Note that the DCC implies that G has a circuit which has distance at most one to every vertex of G. Thirdly, we will study new natural questions concerning cubic graphs which admit a 3-edge coloring. These graphs are thus not snarks. The questions which we consider are also related to one of the strongest versions of the Circuit Double Cover Conjecture (CDCC). CDCC: Every bridgeless graph G contains a list S of circuits of G such that every edge of G is covered by exactly two circuits of S.

The Cycle Double Cover Conjecture (CDCC) is one of the central conjectures in graph theory. It states that every 2-edge connected graph G has a set of cycles such that every edge of the graph is covered by precisely two cycles of the set. Such a set is called a Cycle Double Cover (CDC). The CDCC has been stated officially in the 1970s but it is believed to be older and by its simplicity it could actually be much older. Within this project, we introduced new proof methods and used them to show that the CDCC holds for various interesting classes of graphs. Moreover, we stated several new conjectures. Snarks are special cubic graphs which do no admit a proper 3-edge coloring and they play an essential role in many fundamental problems in graph theory. For instance, it is well known that it suffices to prove the CDCC for snarks in order to prove the entire conjecture. Within this project, we introduced a new class of snarks (Hist-snarks) which are characterized by having a decomposition into a tree and a 2-regular subgraph whose components are called the outer cycles. This tree must be a spanning tree without a vertex of degree two (such tree is called a Hist) and the vertices of the outer cycles must be the leaf vertices of the tree. We characterized the possible occurring lengths of outer cycles of Histsnarks.Moreover, we discovered that every snark with less than 38 vertices is a Hist-snark and that there are infinitely many Hist-snarks. With respect to the CDCC we proved that every Hist-snark with at most three outer cycles has a CDC which even contains all its outer cycles. Then we answered a related open problem. It was asked if every cubic graph G has a decomposition into a tree and a 2-regular subgraph if the cyclic edge connectivity of G is large enough. We showed that this is not the case. It has been conjectured by the project leader that every connected cubic graph has a decomposition into a spanning tree, a 2-regular subgraph and a matching. Note that if the matching is empty, the spanning tree is a Hist. We showed that the conjecture holds for all connected planar cubic graphs. Moreover, we achieved progress on solving problems related to Kotzig frames, 4-flows, cycle permutation snarks and quadrangulations.