File | Description | Format |
---|---|---|
9411593.pdf (4MB) | (no description provided) |
Title: | Topics in extremal graph theory |
Author(s): | Chung, Myung Sook |
Doctoral Committee Chair(s): | West, Douglas B. |
Department / Program: | Mathematics |
Discipline: | Mathematics |
Degree Granting Institution: | University of Illinois at Urbana-Champaign |
Degree: | Ph.D. |
Genre: | Dissertation |
Subject(s): | Mathematics |
Abstract: | New results are proved on several problems in extremal graph theory. Let $ex\sp*(D;H)$ denote the maximum number of edges in a connected graph with maximum degree D and no induced subgraph isomorphic to the graph H. It is shown that this is finite if and only if H is a disjoint union of paths. Several specific forbidden subgraphs H have been studied, and the following results have been proved: (1) $ ex\sp*(D;P\sb4) = D\sp2$ for all D, uniquely achieved by $K\sb{D,D}.$ If, in addition, the maximum clique size is $\omega$, then the number of edges is at most $D\sp2 - {D(\omega-2)\over 2}.$ (2) $ex\sp*(D;P\sb5) = {2\over 27}D\sp3 + O(D\sp2).$ (3) $ex\sp*(D;2P\sb3) = {1\over 8}D\sp4 +{1\over 8}D\sp3 + O(D\sp2).$ (4) $ex\sp*(D;P\sb3 + P\sb2)< 2D\sp2.$ If $K\sb3$ is also forbidden, then $ex\sp*(D;P\sb3 + P\sb2, K\sb3) = {5\over 4}D\sp2 + O(D).$ The p-intersection number of a graph G, denoted by $\theta\sb{p}(G),$ is the minimum size of a set $\cup\sb{v\in V(G)}S\sb{v}$ such that u and v are adjacent if and only if $\vert S\sb{u}\cup S\sb{v}\vert \ge p.$ It is proved here that $\theta\sb{p}(K\sb{n,n})\ge (n\sp2 + (2p - 1)n)/p$ for $p\ge 2.$ Furthermore, $\theta\sb2(K\sb{n,n}) = (n\sp2 + 3n)/2$ is achieved using a graph design called orthogonal double covering. For sufficiently large p, the residual intersection number, denoted by $\theta\sp*(G),$ is defined and studied here as the limiting value of $f\sb{p}(G) = \theta\sb{p}(G)-p.$ The maximum values of n such that $\theta\sp*(K\sb{2,n}) = 5,6$ and 7 are 4, 7, and 14, respectively. Asymptotically, $\theta\sp*(K\sb{2,n}) = \log\sb2 n + o(\log\sb2 n).$ An $(n,m,r)$-rainbow-free coloring is a multi-edge-coloring of edges in $K\sb{n}$ with at most m colors such that the edges of each color form a clique and it is not possible to choose distinct colors for each edge in any r-cycle. The maximum value of the sum of the numbers of colors appearing on each edge over all $(n,m,r)$-rainbow-free colorings, denoted by $e(n,m,r),$ was originally investigated by S. Roman. The bounds he demonstrated have been improved upon in this thesis. It is shown that $e(n,m,3) = 2{n-1\choose 2} + m - 1,$ and that $e(n,m,4)\le 3{n\choose 2} + m.$ |
Issue Date: | 1993 |
Type: | Text |
Language: | English |
URI: | http://hdl.handle.net/2142/22749 |
Rights Information: | Copyright 1993 Chung, Myung Sook |
Date Available in IDEALS: | 2011-05-07 |
Identifier in Online Catalog: | AAI9411593 |
OCLC Identifier: | (UMI)AAI9411593 |