Files in this item

FilesDescriptionFormat

application/pdf

application/pdfMCDONALD-DISSERTATION-2015.pdf (690kB)
(no description provided)PDF

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 Urbana-Champaign
Degree:Ph.D.
Genre:Dissertation
Subject(s):graph theory
vertex ranking
list ranking
on-line 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 node-labeling scheme that models a parallel processing problem. A k-ranking 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 on-line 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 on-line 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 on-line 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 k-colorings 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:2015-07-15
Type:Thesis
URI:http://hdl.handle.net/2142/88024
Rights Information:Copyright 2015 Daniel Cooper McDonald
Date Available in IDEALS:2015-09-29
Date Deposited:August 201


This item appears in the following Collection(s)

Item Statistics