An edge ordering of a graph G = (V,E) is an injection f : E → R, where R denotes the set of real numbers. A path in G for which the edge ordering f increases along its edge sequence is called an f-ascent; an f-ascent is maximal if it is not contained in a longer f-ascent. The depression of G is the smallest integer k such that any edge ordering f has a maximal f-ascent of length at most k. In this dissertation we discuss various results relating to the depression of a graph. We determine a formula for the depression of the class of trees known as double spiders. A k-kernel of a graph G is a set of vertices U ⊆ V (G) such that for any edge ordering f of G there exists a maximal f-ascent of length at most k which neither starts nor ends in U. We study the concept of k-kernels and discuss related depression results, including an improved upper bound for the depression of trees. We include a characterization of the class of graphs with depression three and without adjacent vertices of degree three or higher, and also construct a large class of graphs with depression three which contains graphs with adjacent vertices of high degree. Lastly, we apply the concept of ascents to edge colourings using possibly fewer than |E(G)| colours (integers). We consider the problem of determining the minimum number of colours for which there exists an edge colouring such that the length of a shortest maximal path of edges with increasing colors has a given length. / Graduate / 0405

<p> Let t, k, v be three positive integers such that 2 ≤ t < k ≤ v. A Steiner system S(t, k, v) is a pair (V, B) where |V| = v and B is a collection of k-subsets of V, called blocks, such that every t-subset of V occurs in exactly one block in B. When t = 2, the Steiner system S(2, k, v) is sometimes called a Steiner 2-design.</p> <p> Given a Steiner 2-design, S = (V, B), with general block size k, a block-colouring of S is a mapping ¢ : B ---> C, where C is a set of colours. If |C| = n, then ¢ is an n-block-colouring. In this thesis we focus on block-colourings for Steiner 2-designs with k = 4 with some results for general block size k.</p> <p> In particular, we present known results for S(2, 4, v)s and the classical chromatic index. A classical block-colouring is a block-colouring in which any two blocks containing a common element have different colours. The smallest number of colours needed in a classical block-colouring of a design S = (V, B), denoted by x'(S), is the classical chromatic index.</p> <p> We also discuss n-block-colourings of type π, where π = ( π1, π2, ... , πs ) is a partition of the replication number r = v-1/k-1 for a Steiner system S(2,k,v). In particular, we focus on 8(2,4,v)s and the partitions (2, 1, 1, ... , 1), (3, 1, 1 ... , 1), and partitions of the form π = (π1, π2, ... , πs), where |πj -πil ≤ 1 for all 1 ≤ i < j ≤ s. These latter partitions are called equitable partitions and the corresponding block-colourings are called equitable block-colourings.</p> <p> Finally, we present results on the T-chromatic index for S(2, 4, v )s for various configurations T. The T-chromatic index for a Steiner system S(2, k, v), S, is the minimum number of colours needed to colour the blocks of S such that there are no monochromatic copies of T. In particular, we focus on configurations containing 2 lines and configurations containing 3 lines for both S(2, 4, v)s and general S(2, k, v)s. </p> / Thesis / Doctor of Philosophy (PhD)

The problem we study in this thesis asks under which conditions an r-factorization of Kₘʰ can be embedded into an s-factorization of Kₙʰ. This problem is a generalization of a problem posed by Peter Cameron which asks under which conditions a 1-factorization of Kₘʰ can be embedded into a 1-factorization of Kₙʰ. This was solved by Häggkvist and Hellgren. We study sufficient conditions in the case where s = h and m divides n. To that end, we take inspiration from a paper by Amin Bahmanian and Mike Newman and simplify the problem to the construction of an "acceptable" partition. We introduce the notion of irreducible sums and link them to the main obstacles in constructing acceptable partitions before providing different methods for circumventing these obstacles. Finally, we discuss a series of open problems related to this case.