Files in this item



application/pdf8823280.pdf (3MB)Restricted to U of Illinois
(no description provided)PDF


Title:Graph Labelings
Author(s):Weaver, Margaret Lefevre
Doctoral Committee Chair(s):West, Douglas B.
Department / Program:Mathematics
Degree Granting Institution:University of Illinois at Urbana-Champaign
Computer Science
Abstract:Given an ordering of the vertices of a graph around a circle, a page is a collection of edges forming non-crossing 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 k-tuples 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 k-dimensional bandwidth problem for a graph G is to label the vertices $v\sb{i}$ of G with distinct k-tuples 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 k-dimensional bandwidth of a graph in terms of other graph parameters and we find the bandwidth and k-dimensional bandwidth of several classes of graphs.
For a given nontrivial graph H, an H-forbidden 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 H-forbidden chromatic number of G is the minimum number of colors in an H-forbidden coloring of G. An H-required 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 H-required chromatic number of G is the minimum number of colors in an H-required coloring of G. We find triangle-free graphs with arbitrarily large star-required 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
Description:93 p.
Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1988.
Other Identifier(s):(UMI)AAI8823280
Date Available in IDEALS:2014-12-16
Date Deposited:1988

This item appears in the following Collection(s)

Item Statistics