2026-09-18T22:55:46Z https://www.ideals.illinois.edu/oai-pmh

oai:www.ideals.illinois.edu:2142/22749 2023-07-10 col_2142_5131 col_2142_16340 com_2142_5130 com_2142_16339 com_2142_8903

West, Douglas B. Chung, Myung Sook 2011-05-07T13:50:11Z 2011-05-07T13:50:11Z 10000-01-01 1993 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.$ Made available in DSpace on 2011-05-07T13:50:11Z (GMT). No. of bitstreams: 2 license.txt: 4922 bytes, checksum: 910b249b4beec47e7ab768910c8f966f (MD5) 9411593.pdf: 3581412 bytes, checksum: e982f29369a84e1f1ee2a0521b670a7d (MD5) Previous issue date: 1993 Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by Howard Ding (hding2@illinois.edu) on 2011-05-07T14:59:44Z Item is restricted indefinitely. Restriction data tranferred 2014-07-01T11:28:12-05:00 Original Data Group with Access UIUC Users [automated] Release Date: none Reason: ETDs are only available to UIUC Users without author permission ETDs are only available to UIUC Users without author permission U of I Only AAI9411593 (UMI)AAI9411593 http://hdl.handle.net/2142/22749 eng Copyright 1993 Chung, Myung Sook Mathematics Topics in extremal graph theory text Mathematics Mathematics University of Illinois at Urbana-Champaign Dissertation Ph.D.