In this thesis, we study $r$-graphs, that is, $r$-regular graphs in which the edge boundary of every vertex set of odd cardinality contains at least $r$ edges. A special role among them is played by $r$-graphs of class II, which form a natural generalization of snarks to graphs of higher regularity. Due to their close connections with perfect matchings, edge colouring, and several important open conjectures in graph theory, $r$-graphs represent one of the central structures in this area. We present their characterizations, properties, and constructions, as well as their role in the study of class II graphs. Particular emphasis is placed on two new constructions. The first constructs, from an arbitrary $r$-graph, an $(r+1)$-graph preserving the odd-boundary condition; the resulting graph is always of class I. The second is based on the chaining of dipoles and preserves regularity, the odd-boundary condition, and the graph’s membership in the corresponding chromatic-index class. These constructions yield new families of $r$-graphs and broaden the range of constructive approaches available for their study.
|
