Files in this item
Files  Description  Format 

application/pdf MCDONALDDISSERTATION2015.pdf (690kB)  (no description provided) 
Description
Title:  Competitive versions of vertex ranking and game acquisition, and a problem on proper colorings 
Author(s):  McDonald, Daniel Cooper 
Director of Research:  West, Douglas B. 
Doctoral Committee Chair(s):  Reznick, Bruce 
Doctoral Committee Member(s):  Molla, Theo; Chekuri, Chandra 
Department / Program:  Mathematics 
Discipline:  Mathematics 
Degree Granting Institution:  University of Illinois at UrbanaChampaign 
Degree:  Ph.D. 
Genre:  Dissertation 
Subject(s):  graph theory
vertex ranking list ranking online ranking mixing number game acquisition 
Abstract:  In this thesis we study certain functions on graphs. Chapters 2 and 3 deal with variations on vertex ranking, a type of nodelabeling scheme that models a parallel processing problem. A kranking of a graph G is a labeling of its vertices from {1,...,k} such that any nontrivial path whose endpoints have the same label contains a vertex with a larger label. In Chapter 2, we investigate the problem of list ranking, wherein every vertex of G is assigned a set of possible labels, and a ranking must be constructed by labeling each vertex from its list; the list ranking number of G is the minimum k such that if every vertex is assigned a set of k possible labels, then G is guaranteed to have a ranking from these lists. We compute the list ranking numbers of paths, cycles, and trees with many leaves. In Chapter 3, we investigate the problem of online ranking, which asks for an algorithm to rank the vertices of G as they are revealed one at a time in the subgraph of G induced by the vertices revealed so far. The online ranking number of G is the minimum over all such labeling algorithms of the largest label that the algorithm can be forced to use. We give algorithmic bounds on the online ranking number of trees in terms of maximum degree, diameter, and number of internal vertices. Chapter 4 is concerned with the connectedness and Hamiltonicity of the graph G^j_k(H), whose vertices are the proper kcolorings of a given graph H, with edges joining colorings that differ only on a set of vertices contained within a connected subgraph of H on at most j vertices. We introduce and study the parameters g_k(H) and h_k(H), which denote the minimum j such that G^j_k(H) is connected or Hamiltonian, respectively. Finally, in Chapter 5 we compute the game acquisition number of complete bipartite graphs. An acquisition move in a weighted graph G consists a vertex v taking all the weight from a neighbor whose weight is at most the weight of v. In the acquisition game on G, each vertex initially has weight 1, and players Min and Max alternate acquisition moves until the set of vertices remaining with positive weight is an independent set. Min seeks to minimize the size of the final independent set, while Max seeks to maximize it; the game acquisition number is the size of the final set under optimal play. 
Issue Date:  20150715 
Type:  Thesis 
URI:  http://hdl.handle.net/2142/88024 
Rights Information:  Copyright 2015 Daniel Cooper McDonald 
Date Available in IDEALS:  20150929 
Date Deposited:  August 201 
This item appears in the following Collection(s)

Dissertations and Theses  Mathematics

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