Chain decompositions of graphs
Donald K. Skilton · Bulletin of the Australian Mathematical Society · 1985
A chain is essentially a continuous route in a graph which does not repeat any edge.A chain can be either finite or infinite, and can have 0, 1 or 2 end vertices.A chain decomposition of a graph is a set of chains which partition the edge set of the graph.This thesis is primarily concerned with chain decompositions of countably infinite graphs.We consider both abstract graphs and graphs embedded in surfaces.The introductory chapters are largely the result of joint work of Eggleton and Skilton [I].We begin by laying a foundation of definitions and results for the study of chain decompositions.Next we consider small chain decompositions of graphs.Small decompositions of finite graphs have been fully treated by two fundamental theorems of graph theory, due to Euler [4] and Listing [5].We introduce three kinds of small chain decomposition of infinite graphs, each of which generalizes certain features of the small decompositions of finite graphs.Some results are derived about these new decompositions.Next we use the framework provided by these new decompositions to briefly survey existing chain decomposition results, and formulate what we consider to be the main unsolved problems in this area.One class of chain decomposition results is primarily concerned with the number of chains in a decomposition.In particular, we discuss the characterization of these infinite graphs which are decomposable into just