This thesis generalizes to digraphs certain recent results about graphs. There are special digraphs C such that AxC is isomorphic to BxC for some pair of distinct digraphs A and B. Lovasz named these digraphs C zero-divisors and completely characterized their structure. Knowing that all directed cycles are zero-divisors, we focus on the following problem: Given any directed cycle D and any digraph A, enumerate all digraphs B such that AxD is isomorphic to BxD. From our result for cycles, we generalize to an arbitrary zero-divisor C, developing upper and lower bounds for the collection of digraphs B satisfying AxC isomorphic to BxC.

A cancellation graph G is one for which given any graph C, we have G\times C\cong X\times C implies G\cong X. In this thesis, we characterize all bipartite cancellation graphs. In addition, we characterize all solutions X to G\times C\cong X\times C for bipartite G. A characterization of non-bipartite cancellation graphs is yet to be found. We present some examples of solutions X to G\times C\cong X\times C for non-bipartite G, an example of a non-bipartite cancellation graph, and a conjecture regarding non-bipartite cancellation graphs.

The Probabilistic Method was primarily used in Combinatorics and pioneered by Erdös Pai, better known to Westerners as Paul Erdos in the 1950s. The probabilistic method is a powerful tool for solving many problems in discrete mathematics, combinatorics and also in graph .theory. It is also very useful to solve problems in number theory, combinatorial geometry, linear algebra and real analysis. More recently, it has been applied in the development of efficient algorithms and in the study of various computational problems.Broadly, the probabilistic method is somewhat opposite of the extremal graph theory. Instead of considering how a graph can behave in the extreme, we consider how a collection of graphs behave on 'average' where by we can formulate a probability space. The method allows one to prove the existence of a structure with particular properties by defining an appropriate probability space of structures and show that the desired properties hold in the space with positive probability.(please see PDF for complete abstract)

Shortest-path network analysis was employed to identify novel genes that modulate longevity in the baker’s yeast Saccharomyces cerevisiae. Based upon a set of previously reported genes associated with increased life span, a shortest path network algorithm was applied to a pre-existing protein-protein interaction dataset in order to construct a shortest-path longevity network. To validate this network, the replicative aging potential of 88 single gene deletion strains corresponding to predicted components of the shortest path longevity network was determined. The 88 single-gene deletion strains identified by a network approach are significantly enriched for mutation conferring both increased and decreased replicative life span when compared to a randomly selected set of 564 single-gene deletion strains or to the current data set available for the entire haploid deletion collection. In addition, previously unknown longevity genes were identified, several of which function in a longevity pathway believed to mediate life span extension in response to dietary restriction. This study represents the first biologically validated application of a network construct to the study of aging and rigorously demonstrates, also for the first time, that shortest path network analysis is a potentially powerful tool for predicting genes that function as potential modulators of aging.

An n-dimensional halved cube is a graph whose vertices are the binary strings of length n, where two vertices are adjacent if and only if they differ in exactly two positions. It can be regarded as the graph whose vertex set is one partite set of the n-dimensional hypercube, with an edge joining vertices at hamming distance two. In this thesis we compute the automorphism groups of the halved cubes by embedding them in R n and realizing the automorphism group as a subgroup of GLn(R). As an application we show that a halved cube is a circulant graph if and only if its dimension of is at most four.

Benzenoids are graphs representing the carbon structure of molecules, defined by a closed path in the hexagonal lattice. These compounds are of interest to chemists studying existing and potential carbon structures. The goal of this study is to conjecture and prove relations between graph theoretic properties among benzenoids. First, we generate conjectures on upper bounds for the domination number in benzenoids using invariant-defined functions. This work is an extension of the ideas to be presented in a forthcoming paper. Next, we generate conjectures using property-defined functions. As the title indicates, the conjectures we prove are not thought of on our own, rather generated by a process of automated conjecture-making. This program, named Cᴏɴᴊᴇᴄᴛᴜʀɪɴɢ, is developed by Craig Larson and Nico Van Cleemput.

Cette thèse traite de l'étude des spanneurs multichemins, comme extension des spanneurs de graphes classiques. Un spanneur H d'un graphe G est un sous-graphe couvrant tel que pour toute paire de sommets du graphe a,b « appartient à » V(G) la distance dans le spanneur dh(a,b) n'est pas trop étirée par rapport à la distance dans le graphe d'origine dg(a,b). Ainsi il existe un facteur d'étirement (alpha, beta) tel que pour tout a,b« appartient à »V(G), dh(a,b)« est inférieur ou égal à » alpha dg(a,b)+beta. Motivés par des considérations de routage à plusieurs chemins et après la remarque que le concept de spanneur peut être étendu à toute métrique « non décroissante », nous introduisons la notion de spanneur multichemins. Après une introduction au domaine, nous parlerons des résultats obtenus concernant d'une part les spanneurs multichemins arêtes disjoints et d'autre part les spanneurs multichemins sommets disjoints. / This thesis deals with multipath spanners, as an extension of classical graph spanners. A spanner H of a graph G is a spanning subgraph such that for any pair of vertices a,b « is an element of » V(G) the distance measured in the spanner dh(a,b) isn't too much stretched compared to the distance measured in the original graph dg(a,b). As such there exists a stretch factor (alpha, beta) such that for all a,b« is an element of »V(G), dh(a,b)«is less than or equal to » alpha dg(a,b)+beta. Motivated by multipath routing and after noting that the concept of spanner can be extended to any “non decreasing” metric, we introduce the notion of multipath spanner. After an introduction to the topic, we will show the results obtained. The first part is devoted to edge-disjoint multipath spanners. The second part id devoted to vertex-disjoint spanners.

In this thesis we study sparse classes of graphs and their properties usable for design of algorithms and data structures. Our specific focus is on the con- cepts of bounded expansion and tree-depth, developed in recent years mainly by J. Nešetřil and P. Ossona de Mendez. We first give a brief introduction to the theory as whole and survey tools and results from related areas of parametrised complexity and algorithmic model theory. The main part of the thesis, application of the theory, presents two new dynamic data structures. The first is for keeping a tree-depth decomposition of a graph, the second counts appearances of fixed subgraphs in a given graph. The time and space complexity of operations of both structures is guaranteed to be low when used for sparse graphs. 1

Master of Science / Department of Industrial and Manufacturing Systems Engineering / Todd Easton / Graph theory is a widely researched topic. A graph contains a set of nodes and a set of edges. The nodes often represent resources such as machines, employees, or plant locations. Each edge represents the relationship between a pair of nodes such as time, distance, or cost. Integer programs are frequently used to solve graphical problems. Unfortunately, IPs are NP-hard unless P = NP, which implies that it requires exponential effort to solve them. Much research has been focused on reducing the amount of time required to solve IPs through the use of valid inequalities or cutting planes. The theoretically strongest cutting planes are facet defining cutting planes. This research focuses on the node packing problem or independent set problem, which is a combinatorial optimization problem. The node packing problem involves coloring the maximum number of nodes such that no two nodes are adjacent. Node packings have been applied to airline traffic and radio frequencies. This thesis introduces a new class of graphical structures called suns. Suns produce previously undiscovered valid inequalities for the node packing polyhedron. Conditions are provided for when these valid inequalities are proven to be facet defining. Sun valid inequalities have the potential to more quickly solve node packing problems and could even be extended to general integer programs through conflict graphs.

M.Sc. (Computer Science) / The purpose of this disssertation is to study methods to represent structures in three-dimensions. Due to the fact that chemical molecules are mostly complex three-dimensional structures, we used chemical molecules as our application domain. A literature study of current chemical information systems was undertaken. The whole spectrum of information systems was covered because almost all of these systems represent chemical molecules in one way or another. Various methods of three-dimensional structure representation were found in our literature study. All of these methods were discussed in the context of its own application domain. Structure graph grammars were examined and explained in detail. A small object-based system with structure graph grammars as the underlying principle was developed. We speculated on the use of such "intelligent" graph grammars in structure interpretation and identification. Further research in this area was also identified.