W5×Sn的交叉数

轮W5的六个顶点与另外n个顶点联边得到了一类特殊的图Hn．文中先证明了Hn的交叉数为Z（6,n）＋n＋3[n/2],并在此基础上证明了轮W5与星Sn的笛卡尔积的交叉数为Z（6,n）＋2n＋3[2/2].     

几个六阶图与星S_n的笛卡尔积交叉数

分别连结六阶图G1的6个顶点与其它n个顶点,得到一类特殊的图Hn.运用组合方法、归纳思想及反证法证明了Hn的交叉数为Z(6,n)+2「n/2」,并在此基础上证明G1与星K1,n的笛卡尔积的交叉数为Z(6,n)+2「n/2」;另外,证明了含子图S5的其它6个六阶图与星K1,n的笛卡尔积的交叉数都为Z(6,n)+4「n/2」.     

G7×Sn的交叉数

计算并证明了五阶图G7与星Sn的笛卡尔积交叉数cr(G7×Sn)=Z(5,n)+｜n/2｜,这一结果填补了Mrián Kle(s)(c)关于五阶图与星的笛卡尔积交叉数的一处空白.     

Pm与Wn的笛卡尔积交叉数

给出了一个关于Pm与Wn的笛卡尔积交叉数的上界,并且确定了P1×Wn,P2×Wn和P3×Wn的交叉数.     

与直径有关的上可嵌入图类

通过对边添加一些限制条件,进一步研究了直径为3和4的图的上可嵌入性,得到了一些新的上可嵌入图类.从而综合已有结果,完整地刻画了这类图的上可嵌入性情况.     

W5×Sn的交叉数

轮W5的六个顶点与另外n个顶点联边得到了一类特殊的图Hn．文中先证明了Hn的交叉数为Z（6,n）＋n＋3[n/2],并在此基础上证明了轮W5与星Sn的笛卡尔积的交叉数为Z（6,n）＋2n＋3[2/2].     

一类图在环面上的嵌入

图的亏格分布已被证明为NP难问题,对于大部分图类的亏格分布和完全亏格分布,暂时还没有得到.而图在不同亏格曲面上的不等价的嵌入个数往往有一定的相关关系,因此研究图在小亏格曲面上的嵌入问题对于研究图类的亏格分布也就有着重要意义.本文利用嵌入联树模型得到了由鹅卵石路图添加1条边所得到的一类图nG在环面上的嵌入个数为4n-1+(11n-29)2n-3(n≥2).     

一类剪刀积图H(○)G的亏格

设H和G为连通图,H和G的剪刀积图H(○)G定义为:V(H(○)G)=V(H)×V(G),E(H(○)G)={(u,v) (s,t)| uv∈E(H),st∈E(G)}.利用电压图及其覆盖图的嵌入理论,本文研究了当第一个因子H为一条路,第二个因子G为Cayley图时,这类剪刀积图H(○)G的亏格.本文的结果可视为目前在研究这类图的亏格上的一个补充,且较大程度上推广相关文献的主要结果.     

一个六阶图与路的笛卡尔积交叉数

确定图的交叉数是一个完全NP-问题，因为其难度，所以我们能够确定交叉数的图类很少．本文先构造F×Pn≤2n的一种好画法，由这种好画法计算出Cr（FXP。）≤4n，然后利用数学归纳法证明Cr（F×Pn）≥4n，从而确定了F与Pn的笛卡尔积交叉数即Cr（F×Pn）=4n．     

几乎所有的图是上可嵌入的

给定一概率模型,证明了几乎所有的图均是上可嵌入的。