联图K_(1,1,1,2)+P_n的交叉数

确定图的交叉数是一个NP-完全问题.目前大多数的五阶图与路的联图交叉数已经确定,但是仍有少数复杂的五阶图与路的联图交叉数没有确定.本文深化这方面的研究,在Kleitman给出的完全二部图的交叉数cr(K_(5,n))=Z(5,n)和Ho得到的完全多部图的交叉数cr(K_(1,1,1,2,n))=Z(5,n)+2n的基础上,根据图的结构特点,证明了联图K_(1,1,1,2+P_n的交叉数为Z(5,n)+2n+2.     

一个五阶图与路、圈的联图的交叉数

目前已经确定的两个图的联图的交叉数结果较少.设H是由一个4圈及一个孤立点所构成的5阶图.研究了图H与路、圈的联图的交叉数,得到了cr(H+P_n)=Z(5,n)+[n/2]+l,cr(H+C_n):Z(5,n)+[n/2]+2,其中,P_n与C_n分别表示含n个顶点的路与圈.     

关于一个特殊六阶图与路和圈的联图的交叉数

Garey和Johnson证明了确定图的交叉数问题是一个NP-难问题.目前,已确定交叉数的图类并不多.本文证明了一个特殊6阶图与n个孤立点,路P_n及圈C_n的联图的交叉数分别是cr(Q+nK_1)=Z(6,n)+n;cr(Q+P_n)=Z(6,n)+n+1及cr(Q+C_n)=Z(6,n)+n+3.     

六阶图C_6+3K_2与P_n,C_n的联图交叉数

用P_n表示n个点的路,C_n表示长为n的圈,C_6+3K_2表示圈C_6添加三条相邻的边3K_2=C_3得到的图.在Kleitman给出的完全二部图的交叉数cr(K_(6,n))=Z(6,n)的基础上,得到了特殊六阶图C_6+3K_2与路P_n,圈C_n的联图交叉数分别为Z(6,n)+3[n/2]+2与Z(6,n)+3[n/2]+4.     

一个特殊6点图Q与nK_1,P_n及C_n的联图交叉数

图的交叉数是图的一个重要参数,研究图的交叉数问题是拓扑图论中的前沿难题.确定图的交叉数是NP-难问题,因为其难度,能够确定交叉数的图类很少.通过圆盘画法途径,确定了一个特殊6点图与n个孤立点nK_1,路P_n及圈C_n的联图的交叉数分别是cr(Q+nK_1)=Z(6,n)+2[n/2],cr(Q+P_n)=Z(6,n)+2[n/2]+1及cr(Q+C_n)=Z(6,n)+2[n/2]+3.     

一个6点图与路的联图的交叉数

一个图G的交叉数cr(G)是把图G画在平面上,在所有画法中所产生的最少的交叉数.由于其结构的特殊性,能够确定两个图的联图交叉数的精确值的图类很少.本文通过圆盘画法这一途径,确定了一个特殊6点图与路P_n的联图的交叉数.     

关于交叉数为2的联图

确定图的交叉数是NP-完全问题.Kuratowski定理刻画了平面图的结构特征,而对于交叉数为k(k≥1)的非平面图G的结构特征刻画,目前相关结果甚少.对于交叉数为1的联图G_1∨G_2,我们已经刻画出因子图G_1和G_2满足的充要条件.本文刻画了当△(G_2)≠3且cr(G_1∨G_2)=2时因子图G_1和G_2须满足的充要条件.     

Wm∨Pn的交叉数

在Klesc M给出的联图W_3 V P_n的交叉数的基础上,继续对联图Wm V Pn（m=4,5）的交叉数cr进行了研究,得到了cr（W3 V Pn）=Z（5,n）＋n＋「n/2＋1」以及cr（W5 V Pn）=Z（6,n）＋n＋3[n/2」＋1,n≥2.     

S_m∨P_n与S_m∨C_n的交叉数

本文研究与星图有关的联图的交叉数,得到了对任意的n≥1,当m=3,4,5时,星Sm与路P_n的联图的交叉数;以及对任意的n≥3,当m=3,4时,星S_m与圈C_n的联图的交叉数.     

关于交叉数为1的联图

确定图的交叉数是NP-完全问题.Kuratowski定理刻画了平面图的特征,而结合图的交叉数这一参数来研究非平面图的特征,目前相关结果甚少.本文从联图着手,研究当G_1VG_2的交叉数为1时,刻画出因子图G_1和G_2须满足的充要条件.     

循环图C(10,2)与路P_n的笛卡尔积的交叉数

证明了循环图C(10,2)与路P_n的笛卡尔积的交叉数是10n及循环图C(2m,2)的一点悬挂和两点悬挂的交叉数分别是m,2m.     

K_4∨C_n的交叉数

在KlescM给出的完全图K_4∨P_n的交叉数的基础上,得到了cr(K_4∨C_n)=Z(4,n)+n+4,n≥3.特别地,当n=3时,cr(K_4∨C_3)=cr(K_7)=9,由此得到完全图K_7的交叉数另一种证明方法.     

几类特殊Corona图的b-染色数与b-连续性研究

在一个图G的正常k染色中,如果每一个颜色类中都至少存在一个顶点,使得其在其它的k-1个颜色类中都至少有一个邻居,则称这样的正常k染色为b-染色.一个图G的b-染色数是最大的正整数k,使得用k种颜色能够对G进行b-染色,用b(G)来表示.如果对于任意的正整数k:χ(G)≤k≤b(G),用k种颜色可以对图G进行b-染色,则称图G是b-连续的.设G1与G2为任意图,称图G=G_1·G_2为图G_1与G_2的Corona图,其中G包含G_1的一个拷贝,包含G_2的|V(G_1)|个拷贝,且G_1的第i个顶点与G_2的第i个拷贝的所有顶点都邻接.研究了路图与路图、星形图以及轮图所构成的Corona图P_n·P_m、P_n·K_(1,m)以及P_n·W_(m+1)的m-度,b-染色数与b-连续性.     

书本图与齿轮图的子树计数及渐进密度特性分析

图的子树数拓扑指标对指导可靠性网络设计和分析化合物的物理与化学性质均具有重要意义.本文基于生成函数、结构分析及矩阵映射的方法给出书本图B_(n,2)(n≥2)和齿轮图G_(n,1)(n≥3)的子树数生成函数,并分析了B_(n,2)(n≥2)和G_(n,1)(n≥3)的子树密度的渐进特性,本研究为探索复杂圈图和分子的结构新特性提供了新的视角和方法.     

W_4 ∨ C_n的交叉数

本文研究了五阶图与圈图的联图交叉数.利用假设法和比较法等方法,得到了W4∨Cn的交叉数为Z(5,n)+n+n2+4,并推广了联图交叉数的结果与方法.     

联图的圈基

MacLane于1937年给出了圈基方面的重要定理: 图G是平面图, 当且仅当图G有2-重基. 连通图G_1和G_2的联图G_1\vee G_2指的是在它们的不交并G_1\bigcup G_2上添加边集(u,v)|u\in V(G_1), v\in V(G_2). 对G_1和G_2的联图G_1\vee G_2的圈基重数进行了研究, 得到了一个上界, 改进了Zare的结果. 并在此基础之上, 进一步得到特殊联图C_m\vee C_n的圈基重数的一个上界.     

六阶图Q与星图S_n的积图交叉数

目前关于积图的交叉数的研究已经推广到六阶图与星图的积图.研究得到了一个特殊六阶图Q与n个孤立点nK_1的联图交叉数,然后通过收缩的方法,得到了Q与星图S_n的积图交叉数.     

联图S_5∨C_n的交叉数

两个图G和H的联图,记作G∨H,是指将G中每个点与H中的每个点连边得到的图.本文证明了星图S_5与圈C_n的联图S_5∨C_n的交叉数为Z(6,n)+4[n/2]+3(n≥3),其中Z(m,n)=[m/2][(m-1)/2][n/2][(n-1)/2],m,n为非负整数.     

循环图C(12,2)与路P_n的笛卡尔积的交叉数

循环图C(m,2)表示由圈Cm(v_1v_2…v_mv_1)增加边v_iv_i+2(i=1,2,…,m,i+2(modm))所得到的图,本文证明了循环图C(12,2)与路P_n的笛卡尔积的交叉数是12n.     

K2,3 ∨ Pn的交叉数

已经确定的五阶图与路Pn的联图的交叉数较少,作者继续深化这方面的研究,得到了联图K2,3 V Pn与{K2,3+e}V Pn的交叉数为Z(5,n)+n+1.