Optimal degree conditions for spanning subgraphs
Description
In a large network (graph) it would be desirable to guarantee the existence of some local property based only on global knowledge of the network. Consider the following classical example: how many connections are necessary to guarantee that the network contains three nodes which are pairwise adjacent? It turns out that more than n^2/4 connections are needed, and no smaller number will suffice in general. Problems of this type fall into the category of ``extremal graph theory.'' Generally speaking, extremal graph theory is the study of how global parameters of a graph are related to local properties. This dissertation deals with the relationship between minimum degree conditions of a host graph G and the property that G contains a specified spanning subgraph (or class of subgraphs). The goal is to find the optimal minimum degree which guarantees the existence of a desired spanning subgraph. This goal is achieved in four different settings, with the main tools being Szemeredi's Regularity Lemma; the Blow-up Lemma of Komlos, Sarkozy, and Szemeredi; and some basic probabilistic techniques.
Date Created
The date the item was original created (prior to any relationship with the ASU Digital Repositories.)
2011
Agent
- Author (aut): DeBiasio, Louis
- Thesis advisor (ths): Kierstead, Henry A
- Thesis advisor (ths): Czygrinow, Andrzej
- Committee member: Hurlbert, Glenn
- Committee member: Kadell, Kevin
- Committee member: Fishel, Susanna
- Publisher (pbl): Arizona State University