{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/71268"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/71268","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Graph Labelings","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.","abstract_html":"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.","abstract_has_math":true,"creators":["Weaver, Margaret Lefevre"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Mathematics","degree_department":null,"school":null,"contributors":["West, Douglas B."],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2014,"date_issued":"2014-12-16T06:18:24Z","date_published":"2014-12-16T06:18:24Z","updated_at":"2026-07-22T22:26:04Z","subjects":["Mathematics","Computer Science"],"languages":[],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["(UMI)AAI8823280"],"render_values":[{"text":"(UMI)AAI8823280","href":null,"code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/2142/71268","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["West, Douglas B."]},{"key":"dc:creator","label":"Author","values":["Weaver, Margaret Lefevre"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2014-12-16T06:18:24Z","10000-01-01","1988"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Mathematics"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Mathematics","Computer Science"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/71268","(UMI)AAI8823280"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["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.","Made available in DSpace on 2014-12-16T06:18:24Z (GMT). No. of bitstreams: 1 8823280.pdf: 3251765 bytes, checksum: 08dfde08c225e60f9c7c6e99a63eb327 (MD5) Previous issue date: 1988","Embargo set by: Seth Robbins for item 71434 Lift date: Forever Reason: Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","U of I Only","93 p.","Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1988."]},{"key":"dc:title","label":"Title","values":["Graph Labelings"]}]}],"canonical_facts":{"dc:contributor":["West, Douglas B."],"dc:creator":["Weaver, Margaret Lefevre"],"dc:date":["2014-12-16T06:18:24Z","10000-01-01","1988"],"dc:description":["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.","Made available in DSpace on 2014-12-16T06:18:24Z (GMT). No. of bitstreams: 1 8823280.pdf: 3251765 bytes, checksum: 08dfde08c225e60f9c7c6e99a63eb327 (MD5) Previous issue date: 1988","Embargo set by: Seth Robbins for item 71434 Lift date: Forever Reason: Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","U of I Only","93 p.","Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1988."],"dc:identifier":["http://hdl.handle.net/2142/71268","(UMI)AAI8823280"],"dc:subject":["Mathematics","Computer Science"],"dc:title":["Graph Labelings"],"dc:type":["text"],"thesis:degree_discipline":["Mathematics"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:26:04Z"}