Pagenumber of complete bipartite graphs
Pagenumber of complete bipartite graphs
复制标题
完全二分图的页码
DOI：
10.1002/jgt.3190120403
复制
发表时间：
1988
期刊：
影响因子：
--
通讯作者：
D. West
中科院分区：
文献类型：
--
作者：
D. Muder;Margaret L. Weaver;D. West
给定图的顶点围绕圆的排序，页面是形成不相交弦的边的集合。书嵌入是顶点的循环排列以及将边缘划分为页面。页数t（G）（也称为书厚）是G嵌入的书中的最小页数。本文给出了一个一般的t（Km，n）（m + 2n）/4的构造，我们猜想它是最优的.我们证明了一个结果，表明这是最优的m <$2n − 3。对于最困难的情况m = n，我们考虑规则的顶点排列，即，将来自每个分集的顶点放入相等大小的游程中。这样排序的书嵌入需要<$（7 n − 2）/9页，这是可以实现的。一般结构使用较少的页面，但顺序不规则。
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) (also called book thickness) is the minimum number of pages in a book embedding of G. We present a general construction showing t(Km,n) ⩽ ⌈(m + 2n)/4⌉, which we conjecture optimal. We prove a result suggesting this is optimal for m ⩾ 2n − 3. For the most difficult case m = n, we consider vertex permutations that are regular, i.e., place vertices from each partite set into runs of equal size. Book embeddings with such orderings require ⌈(7n − 2)/9⌉ pages, which is achievable. The general construction uses fewer pages, but with an irregular ordering.