Files in this item
Files  Description  Format 

application/pdf 8823280.pdf (3MB)  (no description provided) 
Description
Title:  Graph Labelings 
Author(s):  Weaver, Margaret Lefevre 
Doctoral Committee Chair(s):  West, Douglas B. 
Department / Program:  Mathematics 
Discipline:  Mathematics 
Degree Granting Institution:  University of Illinois at UrbanaChampaign 
Degree:  Ph.D. 
Genre:  Dissertation 
Subject(s):  Mathematics
Computer Science 
Abstract:  Given an ordering of the vertices of a graph around a circle, a page is a collection of edges forming noncrossing chords. A book embedding is a circular permutation of the vertices together with a partition of the edges into pages. The pagenumber t (G) is the minimum number of pages in a book embedding of G. We present a general construction showing $t(K\sb{m,n}) \leq \lceil(m + 2n)/4\rceil$, which we conjecture to be optimal. We prove a result suggesting this is optimal for $m \geq 2n  3$. For the most difficult case, $m = n$, we consider vertex permutations that are regular, i.e. place the vertices from each partite set into runs of equal size. Book embeddings with such orderings require $\lceil(7n  2)/9\rceil$ pages, which is achievable. The general construction uses fewer pages, but with an irregular ordering. For ktuples of integers $X = (x\sb1,x\sb2,\dots,x\sb{k})$ and $Y = (y\sb1,y\sb2,\dots,y\sb{k})$, let $\vert X  Y\vert$ = $\sum\sbsp{i = 1}{k}\vert x\sb{i}  y\sb{i}\vert$. The kdimensional bandwidth problem for a graph G is to label the vertices $v\sb{i}$ of G with distinct ktuples of integers $f (v\sb{i})$ so that the quantity max $\{\vert f(v\sb{i})  f (v\sb{j}\vert{:}(v\sb{i},v\sb{j}) \in E(G)\}$ is minimized. We find bounds on the kdimensional bandwidth of a graph in terms of other graph parameters and we find the bandwidth and kdimensional bandwidth of several classes of graphs. For a given nontrivial graph H, an Hforbidden coloring of a graph G is an assignment of colors to the vertices of G so that G contains no monochromatic subgraph isomorphic to H. The Hforbidden chromatic number of G is the minimum number of colors in an Hforbidden coloring of G. An Hrequired coloring of G is an assignment of colors to the vertices of G such that every induced monochromatic subgraph of G is a subgraph of H. The Hrequired chromatic number of G is the minimum number of colors in an Hrequired coloring of G. We find trianglefree graphs with arbitrarily large starrequired chromatic numbers and we seek an analogue to Brooks' Theorem for the $P\sb2$required chromatic number, where $P\sb2$ is the path containing two vertices. We also find the generalized chromatic numbers of several classes of graphs, including the Cartesian product of cycles and the complete multipartite graphs, when the forbidden or required configurations are stars or paths. 
Issue Date:  1988 
Type:  Text 
Description:  93 p. Thesis (Ph.D.)University of Illinois at UrbanaChampaign, 1988. 
URI:  http://hdl.handle.net/2142/71268 
Other Identifier(s):  (UMI)AAI8823280 
Date Available in IDEALS:  20141216 
Date Deposited:  1988 
This item appears in the following Collection(s)

Dissertations and Theses  Mathematics

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