Search

A multipartite graph Km₁, m₂, ..., mr (group divisible design GDD) is (t,d)-decomposable if it can be decomposed into t factors with the same diameter d. The graph Km₁, m₂, ..., mr (design GDD) is (t,d)-isodecomposable if the factors are moreover isomorphic. Km₁, m₂, ..., mr (GDD) is admissible for a given t if its number of edges (or blocks) is divisible by t. fr(t,d) or gr(t,d), respectively, is the minimum number of vertices of a (t,d)-decomposable or (t,d)-isodecomposable complete r-partite graph, respectively. gr(t,d) is the minimum number such that for every p ≥ gr(t,d) there exists a (t,d)-isodecomposable r-partite graph with p vertices, and hr(t,d) is the minimum number such that all admissible r-partite graphs with p ≥ hr (t,d) vertices are (t,d)-isodecomposable. We completely determine the spectrum of all bipartite and tripartite (2,d)-isodecomposable graphs. We show that f₂(2,d) = g₂(2,d) = g₂(2,d) =h₂(2,d) and f₃(2,d) = g₃(2,d) = g₃(2,d) for each d, that is possible, while h₃(2,2) = ∞ (i.e., for any given p, there is an admissible graph with more than p vertices which is not (2,2)-isodecomposable), h₃(2,3) = g₃(2,3) +2, h₃(2,4) = g₃(2,4) and h₃(2,5) = g₃(2,5) + 1. For complete four-partite graphs we completely determine the spectrum of (2, d)-isodecomposable graphs with at most one odd part. For the remaining admissible graphs, namely for those with all odd parts, we show that there is no such (2,5)-isodecomposable graph. For d = 2,3,4 we solve the problem in this class completely for the graphs Kn,n,n,m and Kn,n,m,m. For all r ≥ 5 we determine smallest (2,d)-isodecomposable r-partite graphs for all possible diameters and show that also in these cases always gr(2,d) = gr'(2,d). Some values of hr(2,d) are also determined. We furthermore prove that if a GDD with r ≥ 3 groups is (2,d)-isodecomposable, then d ≤ 4 or d = ∞. We show that for every admissible n there exists a (2,3)- and (2,4)-isodecomposable 3 - GDD(n,3), i.e., a GDD with 3 groups of cardinality n and block size 3. Finally, we determine the spectrum of the designs 3 - GDD(n,3) which are decomposable into unicyclic factors. Doctor of Philosophy (PhD)

In this thesis we investigate the existence of a particular class f linear space called an almost uniform linear space. An almost uniform linear space is a linear space in which exactly two lines (called long lines) have sizes u and w, respectively, and all other lines (called short lines) have the same size k (k≥2). We determine the necessary conditions for the existence of an almost uniform linear space, in the cases where the long lines intersect (or are disjoint) and have the same size (or distinct sizes). Next, we are interested in establishing the sufficiency of said conditions for almost uniform linear paces in which the short lines all have size two, three, four, or five. If we assume that the short lines all have size two, this follows immediately. Also, we can show that the conditions are sufficient for almost uniform linear spaces in which the short lines have size three and (i) the two long lines intersect and have the same size u, or (ii) the two long lines intersect (or are disjoint) and have sizes u Є {5,7,9} and w Є {7, 9, 13, 15}, where u ≠ w. By generalizing the conditions in (ii), we provide partial answers to the existence question for almost uniform linear spaces in which one long line has size 6t + 5, 6t + 7 or 6t + 0 (t > 0) and the other long line has size w, w > 6t + r (r = 5,7,9). There are only partial solutions for the case of short lines of size four or five. Doctor of Philosophy (PhD)

In this thesis the concept of selfcomplementary graphs is extended to almost selfcomplementary graphs. We dine a p-vertex graph to be almost selfcomplementary if it is isomorphic to its complement with respect to Kp-e, the complete graph with one edge deleted. An almost selfcomplementary graph with p vertices exists if and only if p=2 or 3 (mod 4), ie., precisely when selfcomplementary graphs do not exist. We investigate various properties of almost selfcomplementary graphs and examine the similarities and differences with those of selfcomplementary graphs. The concepts of selfcomplementary and almost selfcomplementary graphs are combined to define so-called k-selfcomplementary graphs which include the former two classes as subclasses. Although a k-selfcomplementary graph may contain fewer edges than a selfcomplementary or an almost selfcomplementary graph it is found that the former preserves most of the properties of the latter graphs. The notion of selfcomplementarity is further extended to combinatorial designs. In particular, we examine whether a Steiner triple system (twofold triple system, and a Steiner system S(2,4,v), respectively) can be partitioned into two isomorphic hypergraphs. Doctor of Philosophy (PhD)

In this thesis we deal with the following question: given a permutation α on a set V, does there exist a certain block design on V admitting α as an automorphism? We are able to give a (complete or partial) answer to this question for the following: 1) 3- and 4-rotational Steiner triple systems, 2) 3-regular Steiner triple systems, 3) Steiner triple systems with an involution fixing precisely three elements, 4) 1-rotational triple systems, 5) cyclic extended triple systems, 6) 1-, 2- and 3-rotational extended triple systems, 7) 2-, 3- and 4-regular extended triple systems, 8) 1- and 3-rotational directed triple systems, 9) 1-rotational Mendelsohn triple systems, 10) cyclic extended Mendelsohn triple systems, 11) 1-rotational extended Mendelsohn triple systems. We also present a recursive doubling construction for cyclic Steiner quadruple systems, and construct the latter for several orders. Doctor of Philosophy (PhD)