Files in this item
Files  Description  Format 

application/pdf Wenger_Paul.pdf (924kB)  (no description provided) 
Description
Title:  Three Existence Problems in Extremal Graph Theory 
Author(s):  Wenger, Paul S. 
Director of Research:  West, Douglas B. 
Doctoral Committee Chair(s):  Kostochka, Alexandr V. 
Doctoral Committee Member(s):  West, Douglas B.; Furedi, Zoltan; Vijay, Sujith 
Department / Program:  Mathematics 
Discipline:  Mathematics 
Degree Granting Institution:  University of Illinois at UrbanaChampaign 
Degree:  Ph.D. 
Genre:  Dissertation 
Subject(s):  Mathematics
Combinatorics Graph Theory 
Abstract:  Proving the existence or nonexistence of structures with specified properties is the impetus for many classical results in discrete mathematics. In this thesis we take this approach to three different structural questions rooted in extremal graph theory. When studying graph representations, we seek efficient ways to encode the structure of a graph. For example, an {\it interval representation} of a graph $G$ is an assignment of intervals on the real line to the vertices of $G$ such that two vertices are adjacent if and only if their intervals intersect. We consider graphs that have {\it bar $k$visibility representations}, a generalization of both interval representations and another wellstudied class of representations known as visibility representations. We obtain results on $\mathcal{F}_k$, the family of graphs having bar $k$visibility representations. We also study $\bigcup_{k=0}^{\infty} \mathcal{F}_k$. In particular, we determine the largest complete graph having a bar $k$visibility representation, and we show that there are graphs that do not have bar $k$visibility representations for any $k$. Graphs arise naturally as models of networks, and there has been much study of the movement of information or resources in graphs. Lampert and Slater \cite{LS} introduced {\it acquisition} in weighted graphs, whereby weight moves around $G$ provided that each move transfers weight from a vertex to a heavier neighbor. Our goal in making acquisition moves is to consolidate all of the weight in $G$ on the minimum number of vertices; this minimum number is the {\it acquisition number} of $G$. We study three variations of acquisition in graphs: when a move must transfer all the weight from a vertex to its neighbor, when each move transfers a single unit of weight, and when a move can transfer any positive amount of weight. We consider acquisition numbers in various families of graphs, including paths, cycles, trees, and graphs with diameter $2$. We also study, under the various acquisition models, those graphs in which all the weight can be moved to a single vertex. Restrictive local conditions often have farreaching impacts on the global structure of mathematical objects. Some local conditions are so limiting that very few objects satisfy the requirements. For example, suppose that we seek a graph in which every two vertices have exactly one common neighbor. Such graphs are called {\it friendship graphs}, and Wilf~\cite{Wilf} proved that the only such graphs consist of edgedisjoint triangles sharing a common vertex. We study a related structural restriction where similar phenomena occur. For a fixed graph $H$, we consider those graphs that do not contain $H$ and such that the addition of any edge completes exactly one copy of $H$. Such a graph is called {\it uniquely $H$saturated}. We study the existence of uniquely $H$saturated graphs when $H$ is a path or a cycle. In particular, we determine all of the uniquely $C_4$saturated graphs; there are exactly ten. Interestingly, the uniquely $C_{5}$saturated graphs are precisely the friendship graphs characterized by Wilf. 
Issue Date:  20100820 
URI:  http://hdl.handle.net/2142/16739 
Rights Information:  Copyright 2010 Paul S. Wenger 
Date Available in IDEALS:  20100820 
Date Deposited:  201008 
This item appears in the following Collection(s)

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