3,4跳图的平面性

For a graph G of size ε≥1 and its edge-induced subgraphs H1 and H2 of size r(1≤r≤ε), H1 is said to be obtained from H2 by an edge jump if there exist four distinct vertices u,v,w and x in G such that (u,v)∈E(H2), (w,x)∈ E(G)-E(H2) and H1=H2-(u,v)+(w,x). In this article, the r-jump graphs (r≥3) are discussed. A graph H is said to be an r-jump graph of G if its vertices correspond to the edge induced graph of size r in G and two vertices are adjacent if and only if one of the two corresponding subgraphs can be obtained from the other by an edge jump. For k≥2, the k-th iterated r-jump graph Jrk(G) is defined as Jr(Jrk-1(G)), where Jr1(G)=Jr(G).An infinite sequence{Gi} of graphs is planar if every graph Gi is planar. It is shown that there does not exist a graph G for which the sequence {J3k(G)} is planar, where k is any positive integer. Meanwhile,lim gen(J3k(G))=∞,where gen(G) denotes the genus of a graph G, if the sequencek→∞J3k(G) is defined for every positive integer k. As for the 4-jump gra     

图的最大亏格与图的着色数

结合边连通性,本文给出了一个图的Ｂｅｔｔｉ亏数由这个图的补图的着色数所确定的上界式,证明了所给出的上界式是最好的,得到关于图的最大亏格下界的若干新结果．     

我所了解的图论(二) 第二讲 Hamilton骑士

联想古代的象棋,盘上有8×8=64个方格.棋子有国王、主教、骑士、卒等,每个都有其允许的移动规则.这里引出一些我们所熟知的组合问题.例如,有多少个皇后可安置在此棋盘上使得任意两者都不能相互吃掉.从任何一本讲数学游戏的书中都可发现这一问题的解答.当然,下棋本身就是一个组合问题.对于棋盘上任一给定的状态,是否黑、白二方之一准赢?(至少在我们这代不会指望得到解答!)但是,现在我想谈一谈骑士周游旅行问题.骑     

Steinhause棋盘问题的一个推广

In the present paper, a generalization of Steinhaus' chessboard problem of 8 × 8 and that of m×n are given and its solution is proved. Then, Steinhaus' chessboard problem is directly solved as a corollary, and the m>n case is solved immediately.     

ON THE NUMBER OF EULERIAN PLANAR MAPS

This paper presents the number of combinatorially distinct rooted Eulerian planar maps with the number of non-root-vertices and the number of non-root-faces as two parameters. The parametric expressions for determining the number in the loopless Eulerian case are also obtained.     

GENERAL THEORETICAL RESULTS ON RECTILINEAR EMBEDABILITY OF GRAPHS

In the design of certain kinds of electronic circuits the following question arises:given a non-negative integer k, what graphs admit of a plane embedding such that every edge is a broken lineformed by horizontal and vertical segments and having at mort k bends? Any such graph is said tobe k--rectilinear. No matter what k is, an obvious necessary condition for k-rectilinearity is that thedegree of each vertex does not exceed four.Our main result is that every planar graph H satisfying this condition is 3--rectilinear:in fact,it is 2--rectilinear with the only exception of the octahedron. We also outline a polynomial-timealgorithm which actually constructs a plane embedding of H with at most 2 bends (3 bends if H isthe octahedron) on each edge. The resulting embedding has the property that the total number ofbends does not exceed 2n, where n is the number of vertices of H.     

图的上可嵌入性的邻域条件

用NG（u）表示一个图G中任意点u的邻域集．本文主要证明了下述结果：设G是无环图,对G中任意相邻的点u和υ,即uυ∈E（G）,若如下两条件之一满足：（1）|NG(u)∩NG(υ)≥2;（2）G是2-点连通的图,且|NG(u)∩NG(υ)|≥1,则G是上可嵌入的．     

少圈二重覆盖平面近三角剖分图的生成元

令Ｇ为一具有ｎ个节点的平面近三角剖分图,Ｃ为Ｇ的一个少圈二重覆盖（ＳＣＤＣ）．本文首先给出了Ｇ的一些生成元,由此可以得到Ｇ的一个ＳＣＤＣ．若Ｇ为一外平面近三角剖分图,得到 ｜Ｃ｜≤ｎ－２的一充分必要条件;若 Ｇ至少有一个内点,得到｜Ｃ｜≤ｎ－２的一充分条件．     

A graph partition problem

ＡＧＲＡＰＨＰＡＲＴＩＴＩＯＮＰＲＯＢＬＥＭ￥ＬＩＵＴＡＮＰＥＩ（刘彦佩）（ＤｅｐａｒｆｍｅｎｔｏｆＭａｔｈｅｍａｔｉｃｓ,ＮｏｒｔｈｅｒｎＪｉａｏｔｏｎｙＵｎｉｖｅｒｓｉｔｙ,Ｂｅｉｊｉｎｇ１０００４４,Ｃｈｉｎａ）ＡＵＲＯＲＡＭＯＲＧＡＮＡ（Ｄｅ...     

Enumeration of rooted nonseparable outerplanar maps

In this paper, the number of combinatorially distinct rooted nonseparable outerplanar maps withm edges and the valency of the root-face being n is found to be(m-1)! (m-2) !:(n-1)!(n-2)! (m-n)!(m-n 1)!and, the number of rooted nonseparable outerplanar maps with m edges is also determined to be(2m-2)!:(m-1)!m!,which is just the number of distinct rooted plane trees with m-1 edges.