Graph Labelings

Weaver, Margaret Lefevre

Permalink

https://hdl.handle.net/2142/71268 Copy

Description

Title

Graph Labelings

Author(s)

Weaver, Margaret Lefevre

Issue Date

1988

Doctoral Committee Chair(s)

West, Douglas B.

Department of Study

Mathematics

Discipline

Mathematics

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(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 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.

Graduation Semester

1988

Type of Resource

text

Permalink

http://hdl.handle.net/2142/71268

Owning Collections