{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/34341"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/34341","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Degree Ramsey theory, game and Roman domination, and game saturation in graphs","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.\"","abstract_html":""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."","abstract_has_math":false,"creators":["Kinnersley, William"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Mathematics","degree_department":null,"school":null,"contributors":["West, Douglas B.","Kostochka, Alexandr V.","Balogh, József","Jamison, Robert E."],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2012,"date_issued":"2012-09-18T21:12:11Z","date_published":"2012-09-18T21:12:11Z","updated_at":"2026-07-22T22:25:31Z","subjects":["graph theory","graph games","Ramsey theory","domination","saturation"],"languages":["en"],"rights":["Copyright 2012 William Kinnersley"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/34341","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["West, Douglas B.","Kostochka, Alexandr V.","Balogh, József","Jamison, Robert E."]},{"key":"dc:creator","label":"Author","values":["Kinnersley, William"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2012-09-18T21:12:11Z","2012-08"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Mathematics"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["graph theory","graph games","Ramsey theory","domination","saturation"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2012 William Kinnersley"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/34341"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["\"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.\"","Item withdrawn by Mark Zulauf (zulauf@illinois.edu) on 2012-06-27T19:04:55Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 1 Kinnersley_William.pdf: 894508 bytes, checksum: cc36fb2f3aa4f1ac02305366fcb0c4f5 (MD5)","Made available in DSpace on 2012-09-18T21:12:11Z (GMT). No. of bitstreams: 2 Kinnersley_William.pdf: 894522 bytes, checksum: af18e1c99fcee42d4d5c853451023d95 (MD5) license.txt: 4068 bytes, checksum: 64d7a526af8db16eed8fd3f067da4b64 (MD5)"]},{"key":"dc:title","label":"Title","values":["Degree Ramsey theory, game and Roman domination, and game saturation in graphs"]}]}],"canonical_facts":{"dc:contributor":["West, Douglas B.","Kostochka, Alexandr V.","Balogh, József","Jamison, Robert E."],"dc:creator":["Kinnersley, William"],"dc:date":["2012-09-18T21:12:11Z","2012-08"],"dc:description":["\"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.\"","Item withdrawn by Mark Zulauf (zulauf@illinois.edu) on 2012-06-27T19:04:55Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 1 Kinnersley_William.pdf: 894508 bytes, checksum: cc36fb2f3aa4f1ac02305366fcb0c4f5 (MD5)","Made available in DSpace on 2012-09-18T21:12:11Z (GMT). No. of bitstreams: 2 Kinnersley_William.pdf: 894522 bytes, checksum: af18e1c99fcee42d4d5c853451023d95 (MD5) license.txt: 4068 bytes, checksum: 64d7a526af8db16eed8fd3f067da4b64 (MD5)"],"dc:identifier":["http://hdl.handle.net/2142/34341"],"dc:language":["en"],"dc:rights":["Copyright 2012 William Kinnersley"],"dc:subject":["graph theory","graph games","Ramsey theory","domination","saturation"],"dc:title":["Degree Ramsey theory, game and Roman domination, and game saturation in graphs"],"thesis:degree_discipline":["Mathematics"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:25:31Z"}