Files in this item



application/pdfKinnersley_William.pdf (895kB)
(no description provided)PDF


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
Degree Granting Institution:University of Illinois at Urbana-Champaign
Subject(s):graph theory
graph games
Ramsey theory
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 "on-line" 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 4-cycles, we give bounds on the length of the game (assuming optimal play from both players). When the players must avoid 3-vertex 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:2012-09-18
Rights Information:Copyright 2012 William Kinnersley
Date Available in IDEALS:2012-09-18
Date Deposited:2012-08

This item appears in the following Collection(s)

Item Statistics