• Refine Query
  • Source
  • Publication year
  • to
  • Language
  • 1
  • Tagged with
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • About
  • The Global ETD Search service is a free service for researchers to find electronic theses and dissertations. This service is provided by the Networked Digital Library of Theses and Dissertations.
    Our metadata is collected from universities around the world. If you manage a university/consortium/country archive and want to be added, details can be found on the NDLTD website.
1

On the Existence of Loose Cycle Tilings and Rainbow Cycles

January 2019 (has links)
abstract: Extremal graph theory results often provide minimum degree conditions which guarantee a copy of one graph exists within another. A perfect $F$-tiling of a graph $G$ is a collection $\mathcal{F}$ of subgraphs of $G$ such that every element of $\mathcal{F}$ is isomorphic to $F$ and such that every vertex in $G$ is in exactly one element of $\mathcal{F}$. Let $C^{3}_{t}$ denote the loose cycle on $t = 2s$ vertices, the $3$-uniform hypergraph obtained by replacing the edges $e = \{u, v\}$ of a graph cycle $C$ on $s$ vertices with edge triples $\{u, x_e, v\}$, where $x_e$ is uniquely assigned to $e$. This dissertation proves for even $t \geq 6$, that any sufficiently large $3$-uniform hypergraph $H$ on $n \in t \mathbb{Z}$ vertices with minimum $1$-degree $\delta^1(H) \geq {n - 1 \choose 2} - {\Bsize \choose 2} + c(t,n) + 1$, where $c(t,n) \in \{0, 1, 3\}$, contains a perfect $C^{3}_{t}$-tiling. The result is tight, generalizing previous results on $C^3_4$ by Han and Zhao. For an edge colored graph $G$, let the minimum color degree $\delta^c(G)$ be the minimum number of distinctly colored edges incident to a vertex. Call $G$ rainbow if every edge has a unique color. For $\ell \geq 5$, this dissertation proves that any sufficiently large edge colored graph $G$ on $n$ vertices with $\delta^c(G) \geq \frac{n + 1}{2}$ contains a rainbow cycle on $\ell$ vertices. The result is tight for odd $\ell$ and extends previous results for $\ell = 3$. In addition, for even $\ell \geq 4$, this dissertation proves that any sufficiently large edge colored graph $G$ on $n$ vertices with $\delta^c(G) \geq \frac{n + c(\ell)}{3}$, where $c(\ell) \in \{5, 7\}$, contains a rainbow cycle on $\ell$ vertices. The result is tight when $6 \nmid \ell$. As a related result, this dissertation proves for all $\ell \geq 4$, that any sufficiently large oriented graph $D$ on $n$ vertices with $\delta^+(D) \geq \frac{n + 1}{3}$ contains a directed cycle on $\ell$ vertices. This partially generalizes a result by Kelly, K\"uhn, and Osthus that uses minimum semidegree rather than minimum out degree. / Dissertation/Thesis / Doctoral Dissertation Mathematics 2019

Page generated in 0.038 seconds