Topics in trivalent graphs

[摘要] Chapter 0 details the notation and terminology used. Chapter 1 introduces the usual linear algebra over GF2 of edge space E and its orthogonal subspaces Z (cycle space) and Z* (cut space). "Reduced vectors" are defined as elements of the quotient space E/Z*. Reduced vectors of edges give a simple way of characterising edges that are bridges (their reduced vector is null) or 2-edge cuts (their vectors are equal), and also of spanning trees (the edges outside the tree are a basis) and form to the best of my knowledge a new approach. They are also useful in later chapters to describe Tait colorings, as well as cycle double covers. Perhaps the most important property of E/Z* is the Unique graph theorem: unlike in E, a list of which reduced vectors are edges uniquely determines graph structure (if edge connectivity is high enough; that covers certain “solid” components every trivalent graph can be decomposed into). Chapter 2 gives a brief intoduction to graph embeddings and planar graphs. Chapter 3 deals specifically with trivalent graphs, listing some of the ways in which they are different from graphs in general. Results here include two versions of Bipolar growth theorem which can be used for constructive proofs, and (after defining “halftrees” and a “flipping” operation between them) a theorem enumerating the set C\(_n\) of halftrees of a given size, the "Caterpillar theorem" showing C\(_n\) is connected by flipping, and the "Butterfly theorem" derived from it. Graphs referred to here as "solid" are shown to play an important structural role. Chapter 4 deals with the 4-coloring theorem. The first half shows the older results in a unified light using edge spaces over GF4. The second half applies methods from coding theory to this. The 4-color theorem is shown to be equivalent to a variety of statements about cycle-shaped words in codes over GF4 or GF3, many of them tantalisingly simple to state (but not, as yet, to prove). Chapter 5 deals with what has been variously called polyhedral decompositions and (specifically for those using cycles) cycle double covers, as in the cycle double cover conjecture. The more general concept is referred to as a "map" in this paper, and identified with what is termed here "cisness structures", which is a new approach. There is also a simpler proof of a theorem by Szekeres. Links with the subject of the previous chapter are identified, and some approaches towards proving the conjecture suggested. Several planned appendices were left out of the version submitted for examination because they would make the thesis too big, and/or were not finished. Of the ones that remain, appendix H (on embedding infinite 4- and 3-valent trees X and Y in the hyperbolic plane) now seems disjointed from the body of the text (a planned appendix dealt with colorings of finite graphs as the images of homomorphisms from embeddings of Y). Appendix B enumerates cycle maps (cycle double covers) on a number of small graphs while appendix D investigates the dimension of the instersection of Z and Z*.

[发布机构] University:University of Birmingham;Department:School of Mathematics

[关键词] Q Science;QA Mathematics