k → 1 functions between graphs

Abstract

A function between graphs (considered as subsets of IR.3) is k ~ 1 if each point in the codomain has precisely k pre-images in the domain. The object of this thesis is to consider conditions under which these functions can or cannot exist as their domain and/or codomain ranges over graphs with specific properties, starting from the simplest of cases (K2, an interval) and running progressively to arbitrary complete graphs. When the existence problem is solved in the affirmative, constructions for corresponding functions are exhibited. The study of k ~ 1 functions between graphs knows its birth back in the 1940s, when Harrold showed that the simplest graph K2 consisting of two adjacent vertices (i. e. an arc) cannot be mapped 2 ~ 1 onto any topological space. Since then, many researchers have produced results on k ~ 1 functions where the domain and range of these functions have roved from arcs to circles, trees and, more generally, graphs. In Chapter 1 we establish a few basic properties and give some definitions of terms that will be used in later chapters. In this first chapter, we define three important functions which are used repeatedly throughout this work. In Chapter 2, we analyse intervals which allow continuous functions, and, hence finitely discontinuous functions to be defined on them. We consider also maps from arcs onto the circle and the figure '8' graph, and present a new result on the latter case. Most of the results of Chapter 2 will be used in the discussion about continuous k ~ I maps defined from and onto trees (that is, graphs without any cycles), which make up Chapter 3 and Chapter 4. A complete characterisation of trees that allow 3-to-1 maps onto the simplest graph with a cycle (that is, the circle itself) will be presented. We develop and present also a conjecture for a complete characterisation of trees that allow 4 ~ 1 maps onto the circle. In Chapter 5, we present some necessary and sufficient conditions that two graphs must satisfy in order that a continuous k ~ 1 map can exist between them. The bulk of the original work in this thesis is presented in Chapter 6. Here, for the first time, we derive the initial even value of k for which there exists a k ~ 1 map between two complete graphs both having an even number of vertices, and we construct the appropriate mappings. We also state some known results about k ~ 1 maps between complete graphs and put forward some conjectures which we will be considering in future work.