Three Existence Problems in Extremal Graph Theory
Paul S. Wenger · Illinois Digital Environment for Access to Learning and Scholarship (University of Illinois at Urbana-Champaign) · 2010
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 repre-sentations and another well-studied class of representations known as visibility representations. We obtain results on Fk, the family of graphs having bar k-visibility representations. We also study k=0Fk. 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