Games on graphs, visibility representations, and graph colorings

Wise, Jennifer Irene

Permalink

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

Description

Title

Games on graphs, visibility representations, and graph colorings

Author(s)

Wise, Jennifer Irene

Issue Date

2016-05-11

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

West, Douglas B.

Doctoral Committee Chair(s)

Kostochka, Alexandr

Committee Member(s)

• Chekuri, Chandra
• Molla, Theodore

Department of Study

Mathematics

Discipline

Mathematics

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

• Graphs
• Game Matching
• Game $f$-Matching
• Fool's Solitaire
• Bar Visibility Representations
• $r$-Dynamic Coloring
• Antipodal Edge-Coloring
• $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 f-matching 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 f-matching game on a graph G, denoted (G,f), players Max and Min alternately choose edges of G to build an f-matching; the game ends when the chosen edges form a maximal f-matching. Max wants the final f-matching to be large; Min wants it to be small. The f-matching number is the size of the final f-matching under optimal play. We extend to the f-matching game a lower bound due to Cranston et al. on the game matching number. We also consider a directed version of the f-matching 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 3-vertex 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 t-bar 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 t-bar visibility representation. Let Q_n denote the n-dimensional hypercube. A simple application of Euler's Formula yields b(Q_n) ≥ ⌈(n+1)/4⌉. To prove that equality holds, we decompose Q_{4k-1} 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 r-dynamic if for each v ∈ V (G), at least min{r, d(v)} colors appear in N_G(v). We investigate r-dynamic 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 edge-coloring of Q_n is a 2-coloring of the edges in which antipodal edges have different colors. DeVos and Norine conjectured that for n ≥ 2, in every antipodal edge-coloring 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 A-cordial 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 edge-labeling on G; the edge uv receives the label f(u) + f(v). A graph G isA-cordial if there is a vertex-labeling 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 non-cyclic group is V_4 (also known as Z_2×Z_2). We investigate V_4-cordiality of many families of graphs, namely complete bipartite graphs, paths, cycles, ladders, prisms, and hypercubes. Finally, we introduce a generalization of A-cordiality involving digraphs and quasigroups, and we show that there are infinitely many Q-cordial digraphs for every quasigroup Q."

Graduation Semester

2016-08

Type of Resource

text

Permalink

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

Copyright and License Information

Copyright 2016 Jennifer Irene Wise.

Owning Collections