完全二部图Kn,n书表示的最小页

摘要：作者在本文中简单介绍了图的书表示的相关定义及一些性质，同时给出了详细的证明。本文在偶数个顶点完全图书表示关于最小页的研究的基础上，主要研究了完全二部图Kn,n的书表示最小页的数目。

关键词：完全二部图 书表示 最小页

1.引言

Kobayashi在文献[1]和[2]给出了一些图在三空间的嵌入。他介绍了局部不缠结图及全局不缠结图的感念，同时给出了一个任意图都有的这种嵌入，并且这种嵌入方式有很多很好的性质。

Kobayashi介绍的嵌入，即书表示，是图的很好的一种表示。在[1]中，我们可以了解到一些图的书表示的定义及一些性质。文献[3]给了我们有偶数个顶点的完全图书表示的最小页及其证明。

在本文中简单介绍了图的书表示的相关定义及一些性质，并给出完全二部图的书表示最小页的数目。

2.预备知识

我们将一个图G记为，(V,E)其中V是一个集合，V中的元素称为图的顶点。E为V×V的一个子集，E中的元素称为图的边。

图顶点的集合记为V(G)，边的集合记为E(G)。当V(G)和V(G)都是有限集时，我们称图G为有限图，否则G称为无限图。这篇论文我们主要研究有限图。

定义1[4]若图Kij的顶点集可分成两个子集V1,V2(即满足V1YV2=V,V1IV2=φ）其中V1有i个顶点V2中有j个顶点，若在某一子集中的任意顶点只与另一子集中任意顶点有边相连，与本集合中的顶点无边相连，则称图Ki,j为完全二部图。

我们称 为一本书。令 ，

我们称E为书Bn的联结。令 ，我们称Pi为书Bn的第i-页。

因此我们称 为一本有n页 和联结E的书。

Figure 1 一本有三页的书

定义2.2[1]令 为一个嵌入，且满足

（1）

（2）取任何边 ，我们有 或存在Pi使得，

（3）至少存在G中一条边e使得 。

则称 (或者嵌入φ〕为一个图G的有n页的书表示。

显然 。当n取最小值时，称 为图G的一个最小页的书表示。

定义2.3[1]G为一个有限图，若G中存在一个简单的路边径包含G的所有的顶点，则称这个路径为一个Hamilton路径，称G为一个Peseudo Hamiltonion。若G中存在一个简单闭路径包含G的所有顶点，则称其为一个Hamiltonion圈。令为一个Hamiltonion路径，如果存在书表示 满足 ,则称

为一个以Hamilton路径为依据的书表示，简称为B.P.H.。

引理2.4[1]假设 为完全图的一个B.P.H.,则BP的任意一个页上都不可能包含(n-1)条边。

证明：在此页上至少有一个点是取不到的，否则必有两边相交，这两边不能同时在此页上（如图1）。

Figure2:取不到的点

我们想让更多的边在此叶上，则尽可能的让各个点通过更多的边，但此过程中边必不能相交。故只能如图2增加边，否则必会出现新的取不到的顶点。因为每增加一个边必会用掉一个未取到的顶点，而将第一条边放置好后，还余下(n-3)个顶点，故此页上有n-3+1=n-2条边。即任意一个页上都不可能包含(n-3)条边。

Figure:3边的放置

引理2.5[1]假设 为完全图的一个B.P.H.,则至多有一页包含(n-2)条边。

证明：由引理2.4我们知道每页上最多只能有(n-2)条边，下面我们证这样的页只有一个。

因为(1,n)这条边可以在任意一页上，若我们想取到有最多(n-2)条边的页，则边(1,n)必在此页上。又(1,n)这条边只能在一页上，故则至多有一页包含(n-2)条边。

引理2.6[1]令Kn为一个n个顶点的完全图， 为完全图的一个P-页的B.P.H.,则对于n≥4有 ,当n=3时p=1。其中k表示小于等于k的最大整数。

证明：因为 为完全图的一个B.P.H.，故已经有n-1条边在联结E上，则余下边有 条。又每一页上至少有一条边，故 。

由引理2.5知至多有一页包含(n-2)条边，则其他页至多有(n-3)条边，且余下(p-1)页，则我们有：

又p为整数，故 。

当n=3时，如图3所示只需要一页，即p=1。

Figure4: n=3,n=1

3.定理

定理: 若完全二部图Kn,n中存在一个Hamiltonγ使得为γ去掉一个边的路径，则Kn,n的B.P.H.的书表示的最小页数为n。

证明：我们将完全二部图Kn,n的两组顶点记为

我们要将放在书表示的联结上，则不失一般性的,取上的顶点依次为。为方便下面证明，我们将V1中顶点下脚标全用奇数表示，V2中顶点下脚标全用偶数表示，则上的顶点依次为

。给定一个边 ，我们定义边 的长度为 ，将长度J为的一组边记为E(J)。下面我们分成两种情况讨论最小页的情况：

（1）当n为奇数时，不妨设n=2m+1，则上的顶点依次为

我们考虑如下一组边， 这些边两两不可放在同一平面内，故这2m+1条边需放在2m+1=n个页上，对应分别放在页p1,p2,…，pn上。所以当n为奇数时，完全二部图Kn,n至少需放在n个不同页上，即完全二部图Kn,n的书表示至少有n个页。

(2) 当为偶数时，不妨设n=2m，则上的顶点依次为

首先，我们考虑如下一组边，

这些边两两不可放在同一平面内，故这2m-1条边需放在2m-1个页上，对应分别放在页p1,p2,…，p2m-1上，为此完全二部图Kn,n书表示的其中2m-1个页 。

其次，我们考虑如下这组边，

我们将这组边放到上述完全二部图Kn,n的书表示中，若我们将其放在以上已固定的2m-1上，我们有：

...

则 而

; 无法放在这2m-1页上，所以至少需要放在2m=n页上。所以当n为偶数时，完全二部图Kn,n至少需放在n个不同页上，即完全二部图Kn,n的书表示至少有n个页。

下面证明我们可以找到一个n个页的书表示。因为K2n的B.P.H.的书表示的最小页数为n，且有22n种嵌入方式[3]。而Kn,n与K2n有相同数目的顶点，并且Kn,n的边少于K2n，故Kn,n一定存在n页的书表示。

参考文献：

[1]KOBAYSHI K. Stan dard spatial graph[J].1992.21(1)：117-140

[2]KOBAYSHI K.Book presentation and local unknottedress of spatial graphs [J] Kobe J. Math 1993,10(2):161-171

[3]YIN XUN BO, LI LONG GANG,LEI FENG CHUN, The Uniqueness of Book Presentation of Complete Graph Km,m.Journal of Mathematical Research and Exposition.2009,29(3):407-414

[4]Colin C. Adams, The Knot Book, W. H. Freeman and Company New York,215-229