Given a graph G, a K_3-decomposition of G, also called a triangle decomposition, is a set of subgraphs isomorphic to K_3 whose edges partition the edge set of G. Further, a rational K_3-decomposition of G is a non-negative rational weighting of the copies of K_3 in G such that the total weight on any edge of G equals one. In this thesis, we explore the problem of rational triangle decompositions of dense graphs.
We start by considering necessary conditions for a rational triangle decomposition, which can be represented by facets of a convex cone generated by a certain incidence matrix. We identify several infinite families of these facets that represent meaningful obstructions to rational triangle decomposability of a graph. Further, we classify all facets on up to 9 vertices and check all 8-vertex graphs of degree at least four for rational triangle decomposability. As the study of graph decompositions is closely related to design theory, we also prove the existence of certain types of designs.
We then explore sufficient conditions for rational triangle decomposability. A famous conjecture in the area due to Nash-Williams states that any sufficiently large graph (satisfying some divisibility conditions) with minimum degree at least 3/4v is K_3-decomposable; the same conjecture stands for rational K_3-decomposability (no divisibility conditions required). By perturbing and restricting the coverage matrix of a complete graph, we show that minimum degree of at least 22/23v is sufficient to guarantee that the given graph is rationally triangle decomposable. This density bound is a great improvement over the previously known results and is derived using estimates on the matrix norms and structures originating from association schemes.
We also consider applications of rational triangle decompositions. The method we develop in the search for sufficient conditions provides an efficient way to generate certain sampling plans in statistical experimental design. Furthermore, rational graph decompositions serve as building blocks within certain design-theoretic proofs and we use them to prove that it is possible to complete partial designs given certain constraints. / Graduate / 0405
| Identifer | oai:union.ndltd.org:uvic.ca/oai:dspace.library.uvic.ca:1828/5665 |
| Date | 04 September 2014 |
| Creators | Garaschuk, Kseniya |
| Contributors | Dukes, Peter |
| Source Sets | University of Victoria |
| Language | English, English |
| Detected Language | English |
| Type | Thesis |
| Rights | Available to the World Wide Web, http://creativecommons.org/licenses/by-nc/2.5/ca/ |
Page generated in 0.0026 seconds