#### Withdraw

Loading…

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

#### Kinnersley, William

Loading…

## Permalink

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

## 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

##### Graduate Dissertations and Theses at Illinois PRIMARY

Graduate Theses and Dissertations at Illinois#### Manage Files

Loading…

#### Edit Collection Membership

Loading…

#### Edit Metadata

Loading…

#### Edit Properties

Loading…

#### Embargoes

Loading…