多重闭梯图在曲面上嵌入的分类

利用刘彦佩提出的嵌入的联树模型,得到了二重闭梯图在可定向曲面上的亏格分布的一个递推关系,并进一步给出了多重闭梯图在射影平面上的嵌入个数.     

一类循环图在射影平面上的嵌入北大核心CSCD

嵌入的联树模型是研究图的曲面嵌入的一种有效方法,尤其能方便快捷地研究图在球面,环面,射影平面,Klein瓶上的嵌入。此方法通过合理选择生成树,得到联树和关联曲面,然后对关联曲面进行计数,计算出图在曲面上的嵌入个数.本文利用嵌入的联树模型得出了循环图C(2n+1,2)(n>2)在射影平面上的嵌入个数.     

射影平面上标号图的辅助图

刘彦佩教授给出了平面图的辅助图.推广平面图的辅助图到射影平面,给出标号图的射影平面性的如下刻画:给定标号图$G$对应的辅助图是平衡的当且仅当$G$是射影平面图.     

多重圈梯图在射影平面上的嵌入个数

图在不同亏格曲面上的嵌入个数常常有相关关系,因此,分析一些图类在小亏格曲面上的嵌入个数对最终确定图的亏格分布和完全亏格分布有着重要意义,本文利用嵌入的联树模型得出了多重圈梯图在射影平面上的嵌入个数.     

K_(1,4)梯图的可定向嵌入亏格分布

本文主要运用刘彦佩提出的联树嵌入法研究一类新图-K_(1,4)梯图W_n的可定向嵌入亏格分布,并通过进一步递推化简,得到了K_(1,4)梯图在小亏格上的嵌入亏格多项式显式,以及在其他亏格上的简单递推式,使其在可定向亏格上的嵌入个数更容易地得出.     

扇图在曲面上嵌入的分类

图在曲面上嵌入的分类就是确定图在同一曲面上(不等价的)嵌入的数目.本文,利用刘彦佩提出的嵌入的联树模型,得到了双极图与扇图的关联曲面之间的关系,进而由已知结论的双极图的亏格分布和完全亏格分布推导出扇图的亏格分布和完全亏格分布,并给出了扇图在亏格为1-4的不可定向曲面上嵌入的个数的显式.     

n阶仿射平面上d-disjunct矩阵的讨论

分组测试的NGT算法在许多领域有着广泛的应用,它的数学模型是d-disjunct矩阵.近年来,人们借助于复形理论、图理论、空间理论和容错估算等来研究它.介绍了分组测试和仿射平面的基本知识,在n阶仿射平面上构作了d-disjunct矩阵,证明了它的一些性质,与n阶射影平面上的d-disjunct矩阵作了比较.     

射影平面在R~4的嵌入

射影平面在Ｒ４的嵌入邱允安（上海市建承中学）射影平面Ｐ２是近代数学的一个重要概念．比如对紧致曲面作拓扑分类时，ｎ个射影平面的连通和就构成了曲面的一个大类：不可定向曲面．射影平面的定义是１°将一个元片所有的对径点粘合而得．或２°将一个元片的边界粘合上一...     

Ford-Fulkerson算法与嵌入图中的短圈

关于嵌入图中最短圈的多项式算法的存在性问题,是由Thomassen最早提出的.本文通过改进的Ford-Fulkerson算法,可以得到最短割算法.另一方面,通过定义嵌入图的几何对偶图及其相应的嵌入系统,得到几何对偶图中的可分离圈就对应于原图中的割;反之,若几何对偶图中的割在原图中对应于-个圈,那么该圈一定可分离.从而在射影平面上解决了Mohar与Thomassen关于是否存在多项式算法寻找短圈的问题.对于-般曲面上嵌入图,只要它的面宽度充分大,那么同样有多项式算法发现最短可收缩圈.     

几种曲面上的方格和三角格的左右路的计数

设G是连通的胞腔嵌入于某闭曲面的图,G的一条左右路是指沿G的边通过交错的选择最左和最右的边作为下一条边走出的一闭途径．本文计数得到了自然嵌入到环面,Klein瓶和射影平面的方格子和三角格子图的左右路数．     

Embedding of circulant graphs and generalized Petersen graphs on projective plane

Both the circulant graph and the generalized Petersen graph are important types of graphs in graph theory. In this paper, the structures of embeddings of circulant graph C(2n + 1; {1, n}) on the projective plane are described, the number of embeddings of C(2n + 1; {1, n}) on the projective plane follows, then the number of embeddings of the generalized Petersen graph P(2n +1, n) on the projective plane is deduced from that of C(2n +1; {1, n}), because C(2n + 1;{1, n}) is a minor of P(2n + 1, n), their structures of embeddings have relations. In the same way, the number of embeddings of the generalized Petersen graph P(2n, 2) on the projective plane is also obtained.     

Polyhedral embeddings in the projective plane

We characterize the graphs that have polyhedral embeddings in the projective plane. We also prove that if one embedding of a graph is polyhedral then all embeddings of that graph are polyhedral.     

A characterization of projective-planar signed graphs

A signed graph has a plus or minus sign on each edge. A simple cycle is positive or negative depending on whether it contains an even or odd number of negative edges, respectively. We consider embeddings of a signed graph in the projective plane for which a simple cycle is essential if and only if it is negative. We characterize those signed graphs that have such a projective-planar embedding. Our characterization is in terms of a related signed graph formed by considering the theta subgraphs in the given graph.     

Closed 2-cell embeddings in the projective plane

An embedding of a multi-graph in a manifold is a closed 2-cell embedding provided the closures of the faces are all closed 2-cells. In this paper we characterized the projective planar multi-graphs that have closed 2-cell embeddings in the projective plane.     

Two maps on one surface

Two embeddings of a graph in a surface S are said to be “equivalent” if they are identical under an homeomorphism of S that is orientation‐preserving for orientable S. Two graphs cellularly embedded simultaneously in S are said to be “jointly embedded” if the only points of intersection involve an edge of one graph transversally crossing an edge of the other. The problem is to find equivalent embeddings of the two graphs that minimize the number of these edge‐crossings; this minimum we call the “joint crossing number” of the two graphs. In this paper, we calculate the exact value for the joint crossing number for two graphs simultaneously embedded in the projective plane. Furthermore, we give upper and lower bounds when the surface is the torus, which in many cases give an exact answer. In particular, we give a construction for re‐embedding (equivalently) the graphs in the torus so that the number of crossings is best possible up to a constant factor. Finally, we show that if one of the embeddings is replaced by its “mirror image,” then the joint crossing number can decrease, but not by more than 6.066%. © 2001 John Wiley & Sons, Inc. J Graph Theory 36: 198–216, 2001     

Bounding the number of embeddings of 5-connected projective-planar graphs

A graph is said to be projective-planar if it is nonplanar and is embeddable in a projective plane. In this paper we show that the numbers of projectiveplanar embeddings (up to equivalence) of all 5-connected graphs have an upper bound c(?120).     

On certain Hamiltonian cycles in planar graphs

The problem is considered under which conditions a 4-connected planar or projective planar graph has a Hamiltonian cycle containing certain prescribed edges and missing certain forbidden edges. The results are applied to obtain novel lower bounds on the number of distinct Hamiltonian cycles that must be present in a 5-connected graph that is embedded into the plane or into the projective plane with face-width at least five. Especially, we show that every 5-connected plane or projective plane triangulation on n vertices with no non-contractible cyles of length less than five contains at least distinct Hamiltonian cycles. © 1999 John Wiley & Sons, Inc. J Graph Theory 32: 81–96, 1999     

Generating closed 2-cell embeddings in the torus and the projective plane

If a graphG is embedded in a manifoldM such that all faces are cells bounded by simple closed curves we say that this is a closed 2-cell embedding ofG inM. We show how to generate the 2-cell embeddings in the projective plane from two minimal graphs and the 2-cell embeddings in the torus from six minimal graphs by vertex splitting and face splitting.