This dissertation is a contribution to two classical areas of graph theory, partitioning the vertex set of a graph into disjoint cycles, and packing trees into graphs. In addition to the original results which appear in two papers, we provide a historical background of each topic and a unifying perspective. Chapter 1 contains historical background going back to Euler, Hamilton, and Cayley who can be considered some of the fathers of these topics. Chapter 2 includes two surveys that show the development of both topics. These surveys contain preliminary results needed in the foregoing. Chapter 3 contains our contribution to the area of disjoint cycles. It is motivated by the following conjecture of El-Zahar. If G is a graph of order n ＝ n1 ＋ n2 ＋ &middot；&middot；&middot； ＋ nk with n2 &ge； 3 1 &le； i &le； k) and the minimum degree of G is at least n1/2＋ n2/2＋&dot；&dot；&dot；＋ nk/2 , then G contains k independent cycles of lengths n1, n2, …, nk, respectively. Several previous results toward the resolution of this conjecture have been attained by Dirac, Corradi and Hajnal, and Wang. Our contribution settles the case where n 1 ＝ n2 ＝ &middot；&middot；&middot； ＝ ns ＝3 1 &le； s &le； k) and ns＋1 ＝ ns ＋2 ＝ &middot；&middot；&middot； ＝ nk ＝ 5. Chapter 4 contains our contribution to the tree packing problem which is motivated in part by the observation that trees with large maximum degree are the major obstacle for achieving the packing. Continuing previous works of Bollabas, Wang, and Sauer and Spencer we prove that two trees T1 and T2 of order n, with Delta ＝ max {Delta T1), Delta T2)}, can be packed into a graph with restrained maximum degree. In particular, we show there is a packing a such that Delta T1 &cup； sigmaT2)) &le； Delta ＋ 2.

In this dissertation we investigate two main topics: minor-minimally 3-connected matroids and characteristic polynomials. Chapter 1 provides a survey of basic concepts from matroid theory that will be referenced in later chapters. The remainder of this dissertation includes the main results, their proofs, as well as motivation of these results. A 3-connected matroid M is minor-minimally 3-connected if, for every e &isin； EM), either M\e or M/e is not 3-connected. In Chapter 2, we review several theorems concerning minor-minimally 3-connected matroids. We also consider a conjecture of Wagner, which is the motivation of our research in this area. We provide a counterexample to Wagners conjecture in this chapter. In Chapter 3 we introduce and prove our main result concerning minor-minimally 3-connected binary matroids. This is a chain-type theorem that offers a characterization of minor-minimally 3-connected binary matroids. As a consequence, one can generate all minor-minimally 3-connected binary matroids starting from MK4 ), the graphic matroid of the complete graph with four vertices, the Fano matroid F7, and its dual. The characteristic polynomial of a rank r matroid M with ground set E is defined as cM,x＝ X&sube；E-1 Xxr-r X. The characteristic polynomial PG x) of a graphic matroid MG) is related to the chromatic polynomial of G by the equation PGx＝xw Gc MG,x where oG) is the number of components of G. In Chapter 4, we present existing results concerning these polynomials, and we prove a broken-circuit theorem for matroids. In Chapter 5, we give new upper and lower bounds for the coefficients of the characteristic polynomial of simple binary matroids. New bounds for the coefficients of the flow polynomials of graphs can be obtained as a direct consequence.

Independence Polynomials have been introduced several times, independently and with various names [6, 8, 9], beginning in the early 1980s. Applications have been found in Molecular Chemistry and Statistical Physics. The purposes of this dissertation include the derivation of tight upper and lower bounds for the coefficients of the independence polynomial of a k-tree: n-ks-1 s &le；fsT kn&le； n-k s where Tkn is a k-tree with n vertices and fs is the coefficient of xs in the independence polynomial of Tkn . All instances of equality at the upper and lower bounds are determined. This result generalizes a theorem of Wingard [21] corresponding to k ＝ 1. A second focus of this dissertation is the exact determination of the independence polynomials in several classes of k-trees, including k, n)-paths, k, n)-stars, and k, n)-spirals, and in some graphs which are closely related to k-trees. These include k, n)-cycles and k, n)-wheels. A third focus is the determination of the independence polynomial in a certain class of well-covered graphs. These graphs are described by a construction in Chapter 4 and their independence polynomials are computed using a very general theorem. In cases where the polynomial can be determined in closed form and its coefficients determined separately, the independence polynomial is used to generate some new combinatorial identities. Finally, the independence structure of the line graph of a 2 x n lattice is considered. While the exact determination of the polynomial remains an open question, the fibonacci number of this graph, that is, the sum of the coefficients of its polynomial, is determined precisely for all n. At the end of this dissertation, some further related research problems are proposed.

Let G be a connected and simply connected semisimple algebraic group over an algebraically closed field of positive prime characteristic. Let L(lambda) and Delta(lambda) be the simple and induced finite dimensional rational G-modules with p-singular dominant highest weight lambda. In this thesis, the concept of Weyl filtration dimension of a finite dimensional rational G-module is studied for some highest weight modules with p-singular highest weights inside the p 2-alcove when G is of type B 2. In Chapter 4, intertwining morphisms, a diagonal G-module morphism and tilting modules are used to compute the Weyl filtration dimension of L(lambda) with lambda p-singular and inside the p2 -alcove. It is shown that the Weyl filtration dimension of L(lambda) coincides with the Weyl filtration dimension of Delta(lambda) for almost all (all but one of the 6 facet types) p-singular weights inside the p2-alcove. In Chapter 5 we study some submodule structures of Weyl (and there translations), Vogan, and tilting modules with both p-regular and p-singular highest weights. Most results are for the p2-alcove only although some concepts used are alcove independent.