Three existence problems in extremal graph theory
by Wenger, Paul Shannahan, Ph.D., UNIVERSITY OF ILLINOIS AT URBANA-CHAMPAIGN, 2010, 123 pages; 3452283
 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 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 bar k-visibility representations, a generalization of both interval representations and another well-studied class of representations known as visibility representations. We obtain results on [special characters omitted], the family of graphs having bar k-visibility representations. We also study [special characters omitted]. 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 [18] introduced 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 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 far-reaching 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 friendship graphs, and Wilf [30] proved that the only such graphs consist of edge-disjoint 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 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 C4-saturated graphs; there are exactly ten. Interestingly, the uniquely C5-saturated graphs are precisely the friendship graphs characterized by Wilf.

 Adviser Douglas B. West School UNIVERSITY OF ILLINOIS AT URBANA-CHAMPAIGN Source DAI/B 72-06, p. , May 2011 Source Type Dissertation Subjects Theoretical mathematics Publication Number 3452283
Access the complete dissertation:

» Find an electronic copy at your library.
 Use the link below to access a full citation record of this graduate work: http://gateway.proquest.com/openurl%3furl_ver=Z39.88-2004%26res_dat=xri:pqdiss%26rft_val_fmt=info:ofi/fmt:kev:mtx:dissertation%26rft_dat=xri:pqdiss:3452283 If your library subscribes to the ProQuest Dissertations & Theses (PQDT) database, you may be entitled to a free electronic version of this graduate work. If not, you will have the option to purchase one, and access a 24 page preview for free (if available).