Files in this item



application/pdf9411593.pdf (4MB)Restricted to U of Illinois
(no description provided)PDF


Title:Topics in extremal graph theory
Author(s):Chung, Myung Sook
Doctoral Committee Chair(s):West, Douglas B.
Department / Program:Mathematics
Degree Granting Institution:University of Illinois at Urbana-Champaign
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
Rights Information:Copyright 1993 Chung, Myung Sook
Date Available in IDEALS:2011-05-07
Identifier in Online Catalog:AAI9411593
OCLC Identifier:(UMI)AAI9411593

This item appears in the following Collection(s)

Item Statistics