Degree Ramsey theory, game and Roman domination, and game saturation in graphs

Kinnersley, William

Permalink

https://hdl.handle.net/2142/34341 Copy

Description

Title

Degree Ramsey theory, game and Roman domination, and game saturation in graphs

Author(s)

Kinnersley, William

Issue Date

2012-09-18T21:12:11Z

Director of Research (if dissertation) or Advisor (if thesis)

West, Douglas B.

Doctoral Committee Chair(s)

Kostochka, Alexandr V.

Committee Member(s)

• West, Douglas B.
• Balogh, József
• Jamison, Robert E.

Department of Study

Mathematics

Discipline

Mathematics

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(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 ""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."

Graduation Semester

2012-08

Permalink

http://hdl.handle.net/2142/34341

Copyright and License Information

Copyright 2012 William Kinnersley

Owning Collections