Thesis (Ph. D.)--West Virginia University, 2005. / Title from document title page. Document formatted into pages; contains vii, 94 p. : ill. (some col.). Vita. Includes abstract. Includes bibliographical references (p. 93-94).

M.Sc. / The aim of this thesis is to investigate the topic of edge-colourings of graphs in the context of hereditary graph properties. We particularly aim to investigate analogues of reducibility, unique factorization and some related concepts. Chapter 1 gives the basic definitions and terminology. A few useful general results are also stated. In Chapter 2 we define and investigate decomposability, the analogue of reducibility. Some general results are first proved, such as that the indecomposability of an additive induced-hereditary property in the lattice of such properties implies that it is indecomposable in a general sense. The decomposability of various specific properties is then investigated in the rest of the chapter. In Chapter 3 we investigate unique decomposability, the analogue of unique factorization. We give examples showing that not every additive hereditary property is uniquely decomposable, and we obtain some results on homomorphism properties which lead to the unique decomposability of Ok. We also consider some related questions, such as cancellation and preservation of strict inclusions. Chapter 4 deals with Ramsey properties. We obtain some general results and, using the so-called partite construction, we obtain a few restricted Ramsey-graph results. As a corollary, we obtain two more unique decomposability results. In Chapter 5 we obtain various bounds involving the property Vk of k-degeneracy. We also investigate the sharpness of these bounds and prove that Vk is indecomposable for every k. Chapter 6 deals with the connection between colourings of infinite graphs and properties of finite graphs. We obtain some extensions of the Compactness Principle and give an example showing that the Compactness Principle can be useful in studying finite graphs.

Ph.D. (Mathematics) / Please refer to full text to view abstract

No description available.

No description available.

No description available.

No description available.

No description available.

Plant location as a centralized planning objective in which some agency has control over most of the system elements can be reduced, in many circumstances, to the problem of finding the medians of a weighted graph. This concept is feasible if it can be assumed that each location sought is constrained to a subset of p nodes on an n node network. This combinatorial programming problem can be formally stated as follows: if G is a weighted graph, [formula omitted] the weighted distance of node [symbol omitted] to node [symbol omitted], and Xp is any set of p nodes on G (x₁, x₂, •••,Xp), then the required set of p nodes Xp∗ on G is the p median of the graph if it satisfies the expression [formula omitted]. Although this objective can be explicitly optimized by branch bound algorithms, those developed to date can become computationally infeasible for some large scale problems. A fast method for estimating the medians of a weighted graph is given which will provide optimal or near optimal solutions on any type of network. The heuristic procedures adopted in this study can be generalized in terms of three basic steps; 1) partition the graph to obtain an initial feasible solution, 2) re-iterate over; step 1 to achieve a local minimum, and 3) perturb this convergence to test for a lower bound. The design of steps 1 and 3 are crucial to the success of the algorithmic method. Two procedures are given for the basic partitioning of the graph, one of which is a modification of a criterion originally developed by Singer (1968) . The other method introduces a node elimination recursion which appears, experimentally, to be the more efficient procedure for certain types of weighted networks. Efficient perturbation methods are developed for testing the lower bounds obtained. The basic model structure is modified by the introduction of heuristics for the constrained plant location problem under a wide variety of restrictions. Numerical procedures are suggested for restricting the search to a subset of m potential plant sites among all n nodes on the network. Heuristics are developed for forcing certain locations into solution, for placing upper bound constraints on plant sizes, and for restricting the maximum link distance over which a particular allocation might be made. Attention is given to the problem of estimating the joint minimization of plant and transportation cost functions over a network surface. For dynamic location-allocation systems an explicit dynamic programming formulation is developed for the optimal sequencing of plant locations over time subject, if necessary, to periodic variations in all cost functions and node weights. An application of the basic median algorithm to the problem of rural hospital locations in Southeast British Columbia is demonstrated, and computer codes are listed for all the specified models. / Arts, Faculty of / Geography, Department of / Graduate

No description available.