Files in this item
Files  Description  Format 

application/pdf 9411593.pdf (4MB)  (no description provided) 
Description
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 UrbanaChampaign 
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(\omega2)\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 pintersection 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)$rainbowfree coloring is a multiedgecoloring 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 rcycle. The maximum value of the sum of the numbers of colors appearing on each edge over all $(n,m,r)$rainbowfree 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{n1\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:  20110507 
Identifier in Online Catalog:  AAI9411593 
OCLC Identifier:  (UMI)AAI9411593 
This item appears in the following Collection(s)

Dissertations and Theses  Mathematics

Graduate Dissertations and Theses at Illinois
Graduate Theses and Dissertations at Illinois