Files in this item
Files  Description  Format 

application/pdf WISEDISSERTATION2016.pdf (792kB)  (no description provided) 
Description
Title:  Games on graphs, visibility representations, and graph colorings 
Author(s):  Wise, Jennifer Irene 
Director of Research:  West, Douglas B 
Doctoral Committee Chair(s):  Kostochka, Alexandr 
Doctoral Committee Member(s):  Chekuri, Chandra; Molla, Theodore 
Department / Program:  Mathematics 
Discipline:  Mathematics 
Degree Granting Institution:  University of Illinois at UrbanaChampaign 
Degree:  Ph.D. 
Genre:  Dissertation 
Subject(s):  Graphs
Game Matching Game $f$Matching Fool's Solitaire Bar Visibility Representations $r$Dynamic Coloring Antipodal EdgeColoring $A$Cordial Labeling 
Abstract:  In this thesis we study combinatorial games on graphs and some graph parameters whose consideration was inspired by an interest in the symmetry of hypercubes. A capacity function f on a graph G assigns a nonnegative integer to each vertex of V(G). An fmatching in G is a set M ⊆ E(G) such that the number of edges of M incident to v is at most f(v) for all v ⊆ V(G). In the fmatching game on a graph G, denoted (G,f), players Max and Min alternately choose edges of G to build an fmatching; the game ends when the chosen edges form a maximal fmatching. Max wants the final fmatching to be large; Min wants it to be small. The fmatching number is the size of the final fmatching under optimal play. We extend to the fmatching game a lower bound due to Cranston et al. on the game matching number. We also consider a directed version of the fmatching game on a graph G. Peg Solitaire is a game on connected graphs introduced by Beeler and Hoilman. In the game, pegs are placed on all but one vertex. If x, y, and z form a 3vertex path and x and y each have a peg but z does not, then we can remove the pegs at x and y and place a peg at z; this is called a jump. The goal of the Peg Solitaire game on graphs is to find jumps that reduce the number of pegs on the graph to 1. Beeler and Rodriguez proposed a variant where we want to maximize the number of pegs remaining when no more jumps can be made. Maximizing over all initial locations of a single hole, the maximum number of pegs left on a graph G when no jumps remain is the Fool's Solitaire number F(G). We determine the Fool's Solitaire number for the join of any graphs G and H. For the cartesian product, we determine F(G ◻ K_k) when k ≥ 3 and G is connected. Finally, we give conditions on graphs G and H that imply F(G ◻ H) ≥ F(G) F(H). A tbar visibility representation of a graph G assigns each vertex a set that is the union of at most t horizontal segments ("bars") in the plane so that vertices are adjacent if and only if there is an unobstructed vertical line of sight (having positive width) joining the sets assigned to them. The visibility number of a graph G, written b(G), is the least t such that G has a tbar visibility representation. Let Q_n denote the ndimensional hypercube. A simple application of Euler's Formula yields b(Q_n) ≥ ⌈(n+1)/4⌉. To prove that equality holds, we decompose Q_{4k1} explicitly into k spanning subgraphs whose components have the form C_4 ◻ P_{2^l}. The visibility number b(D) of a digraph D is the least t such that D can be represented by assigning each vertex at most t horizontal bars in the plane so that uv ∈ E(D) if and only if there is an unobstructed vertical line of sight (with positive width) joining some bar for u to some higher bar for v. It is known that b(D) ≤ 2 for every outerplanar digraph. We give a characterization of outerplanar digraphs with b(D)=1. A proper vertex coloring of a graph G is rdynamic if for each v ∈ V (G), at least min{r, d(v)} colors appear in N_G(v). We investigate rdynamic versions of coloring and list coloring. We give upper bounds on the minimum number of colors needed for any r in terms of the genus of the graph. Two vertices of Q_n are antipodal if they differ in every coordinate. Two edges uv and xy are antipodal if u is antipodal to x and v is antipodal to y. An antipodal edgecoloring of Q_n is a 2coloring of the edges in which antipodal edges have different colors. DeVos and Norine conjectured that for n ≥ 2, in every antipodal edgecoloring of Q_n there is a pair of antipodal vertices connected by a monochromatic path. Previously this was shown for n ≤ 5. Here we extend this result to n = 6. Hovey introduced Acordial labelings as a simultaneous generalization of cordial and harmonious labelings. If S is an abelian group, then a labeling f: V(G) → A of the vertices of a graph G induces an edgelabeling on G; the edge uv receives the label f(u) + f(v). A graph G isAcordial if there is a vertexlabeling such that (1) the vertex label classes differ in size by at most 1, and (2) the induced edge label classes differ in size by at most 1. The smallest noncyclic group is V_4 (also known as Z_2×Z_2). We investigate V_4cordiality of many families of graphs, namely complete bipartite graphs, paths, cycles, ladders, prisms, and hypercubes. Finally, we introduce a generalization of Acordiality involving digraphs and quasigroups, and we show that there are infinitely many Qcordial digraphs for every quasigroup Q. 
Issue Date:  20160511 
Type:  Thesis 
URI:  http://hdl.handle.net/2142/92697 
Rights Information:  Copyright 2016 Jennifer Irene Wise. 
Date Available in IDEALS:  20161110 
Date Deposited:  201608 
This item appears in the following Collection(s)

Dissertations and Theses  Mathematics

Graduate Dissertations and Theses at Illinois
Graduate Theses and Dissertations at Illinois