Thesis--Lutheran University, Waterloo, Ont. / Includes bibliographical references.

Thesis (doctoral)--Rheinischen-Friedrich-Wilhelms-Universität. / "August 1999." Includes bibliographical references (p. 106-109) and index.

Thesis (Ph. D.)--University of Wisconsin--Madison, 1984. / Typescript. Vita. eContent provider-neutral record in process. Description based on print version record. Includes bibliographical references (leaves 83-84).

Thesis (M.S.)--Brigham Young University. Dept. of Mathematics, 2005. / Includes bibliographical references (p. 40).

In this thesis, we investigate the contraction reconstruction conjecture. It states that all simple graphs with at least four edges are reconstructible, that is they are uniquely determined from their collection of single edge contraction minors, called the deck. Similar questions have been studied in the past, the vertex reconstruction conjecture being the most famous. There are usually two steps to show that a class of graph is reconstructible. The first one is to show that the class is recognizable, meaning that it is possible to determine if a graph G belongs to that class by looking at its deck. In order to recognize some classes of graphs, we show that a wide range of graph properties are reconstructible. We investigate the connectivity of graphs, which is useful to recognize disconnected, separable, and 2-connected graphs. We also show that the number of cycles of various lengths, the degree sequence, the number of spanning trees, the planarity, the presence of cliques of various sizes, and the diameter are reconstructible. Knowing the lengths of cycles allows us to recognize the class of bipartite graphs, while knowing the degree sequence allows us to recognize regular graphs. The second step in showing that a class of graph is reconstructible is called weak reconstruction. We say that a class of graph is weakly reconstructible if no two graphs in that class share the same deck. A class of graphs that is both weakly reconstructible and recognizable is reconstructible. In this thesis, we show that disconnected graphs, bipartite graphs, most separable graphs and most 2-edge connected graphs are reconstructible. We also show that distance regular graphs and some cubic graphs are reconstructible. We quickly delve into the theory of probabilities to give a proof that almost all graphs are reconstructible. Finally, the relation between edge contraction and graph automorphisms is studied. We study the automorphism group of a graph in relation to those of its cards. We also study the concept of contraction pseudo-similarity. Two edges are contraction pseudo-similar if they are not similar, but their contractions yield isomorphic graphs. We completely characterize the graphs that contain contraction pseudo-similar edges.

D. Phil (Mathematics) / In this thesis we investigate generalized chromatic numbers in the context of hereditary graph properties. We also investigate the general topic of invariants of graphs as well as graph properties. In Chapter 1 we give relevant definitions and terminology pertaining to graph properties. In Chapter 2 we investigate generalized chromatic numbers of some well-known additive hereditary graph properties. This problem necessitates the investigation of reducible bounds. One of the results here is an improvement on a known upper bound for the path partition number of the property Wk. We also look at the generalized chromatic number of infinite graphs and hereby establish the connection between the generalized chromatic number of properties and infinite graphs. In Chapter 3 the analogous question of the generalized edge-chromatic number of some well-known additive hereditary properties is investigated. Similarly we find decomposable bounds and are also able to find generalized edge-chromatic numbers of properties using some well-known decomposable bounds. In Chapter 4 we investigate the more general topic of graph invariants and the role they play in chains of graph properties and then conversely the invariants that arise from chains of graph properties. Moreover we investigate the effects on monotonicity of the invariants versus heredity and additivity of graph properties. In Chapter 5 the general topic of invariants of graph properties defined in terms of the set of minimal forbidden subgraphs of the properties is studied. This enables us to investigate invariants so defined on binary operations between graph properties. In Chapter 6 the notion of natural and near-natural invariants are introduced and are also studied on binary operations of graph properties. The set of minimal forbidden subgraphs again plays a role in the definition of invariants here and this then leads us to study the completion number of a property.

D.Phil. / Domination in graphs is now well studied in graph theory and the literature on this subject has been surveyed and detailed in the two books by Haynes, Hedetniemi, and Slater [45, 46]. In this thesis, we continue the study of domination, by adding to the theory; improving a number of known bounds and solving two previously published conjectures. With the exception of the introduction, each chapter in this thesis corresponds to a single paper already published or submitted as a journal article. Despite the seeming disparity in the content of some of these articles, there are two overarching goals achieved in this thesis. The rst is an attempt to partition the vertex set of a graph into two sets, each holding a speci c domination-type property. The second is simply to improve known bounds for various domination parameters. In particular, an edge weighting function is presented which has been useful in providing some of these bounds. Although the research began as two separate areas of focus, there has been a fair degree of overlap and a number of the results contained in this thesis bridge the gap quite pleasingly. Specially, Chapter 11 uses the edge weighting function to prove a bound on one of the sets in our most fundamental partitions, while the improvement on a known bound presented in Chapter 7 was inspired by considering the possible existence of another partition. This latter proof relies implicitly on the `almost' existence of such a partition.

No description available.

Measures of similarity play a subtle but important role in a large number of disciplines. For example, a researcher in bioinformatics may devise a new computed measure of similarity between biological structures, and use its scores to infer bio-logical association. Other academics may use related approaches in structured text search, or for object recognition in computer vision. These are diverse and practical applications of similarity. A critical question is this: to what extent can a given similarity measure be trusted? This is a difficult problem, at the heart of which lies the broader issue: what exactly constitutes good similarity judgement? This research presents the view that similarity measures have properties of judgement that are intrinsic to their formulation, and that such properties are measurable. The problem of comparing similarity measures is one of identifying ground-truths for similarity. The approach taken in this work is to examine the relative ordering of graph pairs, when compared with respect to a common reference graph. Ground- truth outcomes are obtained from a novel theory: the theory of irreducible change in graphs. This theory supports stronger claims than those made for edit distances. Whereas edit distances are sensitive to a configuration of costs, irreducible change under the new theory is independent of such parameters. Ground-truth data is obtained by isolating test cases for which a common outcome is assured for all possible least measures of change that can be formulated within a chosen change descriptor space. By isolating these specific cases, and excluding others, the research introduces a framework for evaluating similarity measures on mathematically defensible grounds. The evaluation method is demonstrated in a series of case studies which evaluate the similarity performance of known graph similarity measures. The findings of these experiments provide the first general characterisation of common similarity measures over a wide range of graph properties. The similarity computed from the maximum common induced subgraph (Dice-MCIS) is shown to provide good general similarity judgement. However, it is shown that Blondel's similarity measure can exceed the judgement sensitivity of Dice-MCIS, provided the graphs have both sufficient attribute label diversity, and edge density. The final contribution is the introduction of a new similarity measure for graphs, which is shown to have statistically greater judgement sensitivity than all other measures examined. All of these findings are made possible through the theory of irreducible change in graphs. The research provides the first mathematical basis for reasoning about the quality of similarity judgments. This enables researchers to analyse similarity measures directly, making similarity measures first class objects of scientific inquiry.

The concept of a tree has been used in various areas of mathematics for over a century. In particular, trees appear to be one of the most fundamental notions in computer science. Sequential algorithms for trees are generally well studied. Unfortunately many of these sequential algorithms use methods which seem to be inherently sequential. One of the contributions of this thesis is the introduction of several parallel techniques for the construction of various types of trees and the presentation of new parallel tree construction algorithms using these methods. Along with the parallel tree construction techniques presented here, we develop techniques which have broader applications. We use the Parallel Random Access Machine as our model of computation. We consider two basic methods of constructing trees:tree expansion and tree synthesis. In the tree expansion method, we start with a single vertex and construct a tree by adding nodes of degree one and/or by subdividing edges. We use the parallel tree expansion technique to construct the tree representation for graphs in the family of graphs known as cographs. In the tree synthesis method, we start with a forest of single node subtrees and construct a tree by adding edges or (for rooted trees) by creating parent nodes for some roots of the trees in the forest. We present a family of parallel and sequential algorithms to construct various approximations to the Huffman tree. All these algorithms apply the tree synthesis method by constructing a tree in a level-by-level fashion. To support one of the algorithms in the family we develop a technique which we call the cascading sampling technique. One might suspect that the parallel tree synthesis method can be applied only to trees of polylogarithmic height, but this is not the case.We present a technique which we call the valley filling technique and develop its accelerated version called the accelerated valley filling technique. We present an application of this technique to an optimal parallel algorithm for construction of minimax trees. / Science, Faculty of / Computer Science, Department of / Graduate