Files in this item
Files  Description  Format 

application/pdf Kinnersley_William.pdf (895Kb)  (no description provided) 
Description
Title:  Degree Ramsey theory, game and Roman domination, and game saturation in graphs 
Author(s):  Kinnersley, William 
Director of Research:  West, Douglas B. 
Doctoral Committee Chair(s):  Kostochka, Alexandr V. 
Doctoral Committee Member(s):  West, Douglas B.; Balogh, József; Jamison, Robert E. 
Department / Program:  Mathematics 
Discipline:  Mathematics 
Degree Granting Institution:  University of Illinois at UrbanaChampaign 
Degree:  Ph.D. 
Genre:  Dissertation 
Subject(s):  graph theory
graph games Ramsey theory domination saturation 
Abstract:  We examine several problems in extremal graph theory, emphasizing problems involving games on graphs. In Chapter 2, we study a variant of Ramsey theory, seeking Ramsey hosts with small maximum degree. We focus on finding such hosts for trees and cycles. In Chapter 3 we consider the "online" version of this problem. We model this variant using a game in which a player constructs the host graph edge by edge in response to the actions of an adversary. Again we focus on constructing hosts for trees and cycles. In Chapter 4 we consider a game based on graph saturation. Two players alternately select edges from a host graph without creating any copies of a specific subgraph. One player wants to maximize the size of the graph constructed, while the other wants to minimize it. When the host graph is bipartite and the players must avoid 4cycles, we give bounds on the length of the game (assuming optimal play from both players). When the players must avoid 3vertex paths, the graph produced is necessarily a matching. In this case we bound the length of the game in terms of the maximum size of a matching in the host graph. In Chapter 5 we explore a game based on graph domination. A vertex v dominates vertex w in a graph if w is adjacent or equal to v; a dominating set is a set that dominates all vertices. In this game, two players jointly construct a dominating set S in a graph G by alternately adding vertices; each addition must strictly increase the number of vertices dominated. One player aims to minimize the final size of S, while the other aims to maximize it. We establish several bounds on the length of the game in terms of the minimum size of a dominating set in G. We focus especially on the case where G is a forest. In Chapter 6 we examine a more traditional variant of domination. A Roman dominating function (or RDF) in a graph G assigns 0, 1, or 2 to each vertex so that the vertices with label 2 dominate those with label 0. The weight of an RDF is the sum of the labels used. We provide lower bounds on the weight of an RDF of G in terms of the number of vertices. In particular, we give tight bounds for connected graphs and for graphs with minimum degree at least 2. In Chapter 7 we study a graph coloring problem. Given a graph G, we assign each vertex t colors, requiring that vertices within distance d receive fewer than d common colors. We give upper bounds on the number of different colors required for such an assignment in terms of the maximum degree of G. 
Issue Date:  20120918 
URI:  http://hdl.handle.net/2142/34341 
Rights Information:  Copyright 2012 William Kinnersley 
Date Available in IDEALS:  20120918 
Date Deposited:  201208 
This item appears in the following Collection(s)

Dissertations and Theses  Mathematics

Graduate Dissertations and Theses at Illinois
Graduate Theses and Dissertations at Illinois
Item Statistics
 Total Downloads: 194
 Downloads this Month: 2
 Downloads Today: 0