Probabilistic problems in graph theory
by Johannson, Karen Rosemarie, Ph.D., THE UNIVERSITY OF MEMPHIS, 2011, 113 pages; 3476364
 Abstract: In this thesis, I examine two different problems in graph theory using probabilistic techniques. The first is a question on graph colourings. A proper total k-colouring of a graph G = (V, E) is a map ϕ : V ∪ E → {1, 2, . . . , k} such that ϕ| V is a proper vertex colouring, ϕ|E is a proper edge colouring, and if υ ∈V and υw ∈ E then ϕ(υ) ≠ ϕ(υ w). Such a colouring is called adjacent vertex distinguishing if for every pair of adjacent vertices, u and υ, the set {ϕ(u)} ∪ {uw} : uw ∈ E}, the 'colour set of u', is distinct from the colour set of υ. It is shown that there is an absolute constant C such that the minimal number of colours needed for such a colouring is at most Δ(G) + C. The second problem is related to a modification of bootstrap percolation on a finite square grid. In an n × n grid, the 1 × 1 squares, called sites, can be in one of two states: 'uninfected' or 'infected'. Sites are initially infected independently at random and the state of each vertex is updated simultaneously by the following rule: every uninfected site that shares an edge with at least two infected sites becomes itself infected while each infected site with no infected neighbours becomes uninfected. This process is repeated and the central question is, when is it either likely or unlikely that all sites eventually become infected? Here, both upper and lower bounds are given for the probability that all sites eventually become infected and these bounds are used to determine a critical probability for the event that all sites eventually become infected.

 Adviser Bela Bollobas School THE UNIVERSITY OF MEMPHIS Source DAI/B 72-12, p. , Sep 2011 Source Type Dissertation Subjects Applied mathematics; Mathematics Publication Number 3476364
Access the complete dissertation:

» Find an electronic copy at your library.
 Use the link below to access a full citation record of this graduate work: http://gateway.proquest.com/openurl%3furl_ver=Z39.88-2004%26res_dat=xri:pqdiss%26rft_val_fmt=info:ofi/fmt:kev:mtx:dissertation%26rft_dat=xri:pqdiss:3476364 If your library subscribes to the ProQuest Dissertations & Theses (PQDT) database, you may be entitled to a free electronic version of this graduate work. If not, you will have the option to purchase one, and access a 24 page preview for free (if available).