This dissertation is concerned with the existence and the isomorphism of designs. The first part studies the existence of designs. Chapter I shows how to obtain a design from a difference family. Chapters II to IV study the existence of an affine 3-(p^m,4,λ) design where the v-set is the Galois field GF(p^m). Associated to each prime p, this paper constructs a graph. If the graph has a 1-factor, then a difference family and hence an affine design exists. The question arises of how to determine when the graph has a 1-factor. It is not hard to see that the graph is connected and of even order. Tutte's theorem shows that if the graph is 2-connected and regular of degree three, then the graph has a 1-factor. By using the concept of quadratic reciprocity, this paper shows that if p Ξ 53 or 77 (mod 120), the graph is almost regular of degree three, i.e., every vertex has degree three, except two vertices each have degree tow. Adding an extra edge joining the two vertices with degree tow gives a regular graph of degree three. Also, Tutte proved that if A is an edge of the graph satisfying the above conditions, then it must have a 1-factor which contains A. The second part of the dissertation is concerned with determining if two designs are isomorphic. Here the v-set is any group G and translation by any element in G gives a design automorphism. Given a design B and its difference family D, two topological spaces, B and D, are constructed. We give topological conditions which imply that a design isomorphism is a group isomorphism.

In this paper we extend the study of Heffter arrays and the biembedding of graphs on orientable surfaces first discussed by Archdeacon in 2014. We begin with the definitions of Heffter systems, Heffter arrays, and their relationship to orientable biembeddings through current graphs. We then focus on two specific cases. We first prove the existence of embeddings for every K_(6n+1) with every edge on a face of size 3 and a face of size n. We next present partial results for biembedding K_(10n+1) with every edge on a face of size 5 and a face of size n. Finally, we address the more general question of ordering subsets of Z_n take away {0}. We conclude with some open conjectures and further explorations.

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