两个5阶图与路及圈的联图的交叉数

详细的讨论了和两个5阶图Gi(i=11,14)有关的联图的交叉数,分别是:Gi+Hn,Gi+Pn和Gi+Cn,其中Hn是由n个孤立点构成的图,Pn和Cn分别是含n个点的路和圈.     

Pm∨Cn的点可区别边色数

研究了路和圈的联图的点可区别的边染色,得到了其点可区别的边色数。     

路和偶圈中间图的一般Pebbling数

图G的一个一般pebbling移动是从一个顶点上移走p(p≥2)个pebble,而把其中的一个pebble移到与其相邻的一个顶点上.图G的一般pebbling数fgl(G)是最小的正整数n,使得不管n个pebble如何放置在G的顶点上,总可以通过一系列一般pebbling移动把一个pebble移到图G的任意一个顶点上.文章研究了路和偶圈中间图的一般pebbling数.     

边染色图中的正常染色的路和圈

讨论了无三角形的边染色图中的正常染色的路和圈,在无三角形图中改进了原有的结果。证明了在顶点的最小色度至少为d(d≥2)的条件下,边染色图G或者存在长至少为4d-2的正常染色的路,或者存在长至少为2「2d/3的正常染色的圈。     

■色唯一的充要条件

Pn和Cn分别表示具有n个顶点的路和圈.Un表示由Pn-4的两个1度点分别与两个P3的2度点粘接得到的图.应用图的伴随多项式理论得到了(∪i∈AUi)∪(∪j∈BPj)∪(∪k∈MCk)色唯一的充要条件.     

(￣)(∪I∈A Ui)∪(∪j∈B Pj)∪(∪k∈M Ck)色唯一的充要条件

Pn和Cn分别表示具有n个顶点的路和圈.Un表示由Pn-1的两个1度点分别与两个P3的2度点粘接得到的图.应用图的伴随多项式理论得到了(￣)(∪I∈A Ui)∪(∪j∈B Pj)∪(∪k∈M Ck)色唯一的充要条件.     

手镯图的L(2,1)—标号

为了更好地研究频道分配问题,引入了从顶点集到非负整数集的一个函数,即图的一个L(2,1)—标号。假设最小标号为零,图的L(2,1)—标号数就是此图的所有L(2,1)—标号下的跨度的最小数。对于路和圈[WT]的Cartesian积图的推广图——手镯图的标号数问题,给出了手镯图的定义,即是将拟梯子的两端重合而得到的图形,同时给出了其L(2,1)—标号数的定义,运用顶点分组标号法,根据圈的个数和每个圈的顶点数的不同进行分类讨论,研究结果完全确定了手镯图的L(2,1)—标号数的确切值,丰富了图的种类并完善了标号数理论。     

路和圈的广义Mycielski图的邻和可区别全染色

应用构造染色法,研究了路和圈的广义Mycielski图的邻和可区别全染色,得到了路和圈的广义Mycielski图的邻和可区别全色数.     

Pl∪Cm∪Dn的补图的色等价刻画和色惟一的条件

Pn和Cn分别表示具有n个顶点的路和圈，Dn表示Pn-2的一个1度点粘接K3的一个点得到的图，应用伴随多项式理论研究了Pl∪Cm∪Dn的补图的色性，刻画了它的所有色等价图，并给出了其色惟一的条件.     

路和圈的广义Mycielski图的星色数

简单图的星染色是图的染色理论中的一个重要问题.为了深入研究图的星色数,我们用结构图论的方法,给出了路和圈的广义Mycielski图的星染色方法,得到了路和圈的广义Mycielski图的星色数.     

——（∪↑i∈AUi）∪（∪↑j∈BPj）∪（∪↑k∈MCk）色唯一的充要条件

Pn和Cn分别表示具有n个顶点的路和圈．Un表示由Pn-4的两个1度点分别与两个P3的2度点粘接得到的图．应用图的伴随多项式理论得到了——（∪↑i∈AUi）∪（∪↑j∈BPj）∪（∪↑k∈MCk）色唯一的充要条件．     

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

分别讨论了5阶图G16与nK1,Pn,Cn联图的交叉数,得到cr(G16+nK1)=Z(5,n)+n+n/2,n≥1;cr(G16+Pn)=Z(5,n)+n+n/2+1,n≥2;cr(G16+Cn)=Z(5,n)+n+n/2+3,n≥3,其中nK1是n个孤立点构成的图,Pn,Cn分别是含n个点的路和圈.     

平图的四着色与对偶图的H圈

阐明了平图中的H圈与对偶图顶点四着色的依存关系.提出了平图的顶点四着色和对偶图顶点四着色的具体步骤.介绍了多面体平图的H圈分解与对偶图顶点四着色,以及对偶图的H圈分解与平图的顶点四着色.讨论了平图及对偶图的H圈的个数,森林Fi的个数及顶点四着色方案数.     

几类图的联结数

本文给出了若干完全图的联(nK_r+mK_s),圈、路和完全二部图分别与完全图的补图的字典式积(C_m(K_n)、L_m(K_n)和K_(a,b))以及完全r—部图(K_(n1,n2,…nr))等几类图的联结数。     

有关树的联图的厚度

图G的厚度θ(G)是指图G分解为平面生成子图的最小数,它是度量图的平面性的重要指标.图的厚度不仅仅在理论上有着重要的研究价值,它在超大规模集成电路和网络设计中也有着重要的应用.研究了与树有关的3类联图的厚度,第1类是完全图与树,任意包含n个顶点的图与树的联图;第2类是完全二部图与树的联图;第3类是完全k(k≥3)部图与树的联图.     

路和圈的最优一般Pebbling数

图G的一个一般pebbling移动是从一个顶点移走p(p≥2)个pebble,而把其中的一个移到与其相邻的一个顶点上.图G的一般pebbling数fgl(G)是最小的正整数n,使得不管n个pebble如何放置在G的顶点上,总可以通过一系列一般pebbling移动把一个pebble移到图G的任意一个顶点上.图G的一个分布是可解的,当通过一系列一般pebbling移动,能把一个pebble移到其任意一个顶点上.图G的最优一般pebbling数fgl’(G)是可解分布中最小的,即利用fgl’(G)个pebble以构造一个可解分布,且这时需要的pebble个数最少.本文采用反证法,通过去掉一个顶点,改变路(或圈)为其子图,并选择一个可解分布.而这时所用的pebble数要比其最优一般pebbling数小,得到矛盾,这样就证明了路和圈的最优一般pebbling数.     

图的最长路与最长圈

路和圈是图论最基本的概念之一,Euler图问题和Hamilton问题都可归结为路和圈的研究．此外,路和圈在特定图中存在条件是我们最为关注的问题,而最长路和最长圈的研究更是引人入胜．本文就此问题作了较全面的回顾,并提出一些问题,供研究、探讨。     

基于平图的H圈分解的对偶图的四着色

阐明了平图中的H圈与对偶图中的森林Fi及顶点四着色的依存关系,提出了一种基于H圈分解的任意平图的顶点四着色方法。介绍了20面体平图中的90个H圈及对偶图中的90个森林Fi及90种顶点四着色方案。讨论了平图及对偶图中的H圈Ci的个数,森林Fi的个数和顶点的四着色方案数。     

2类与4-圈有关图的优美性

把顺序有一个公共点的n个4圈的并图记作Fn,4;图Fn,4每个4圈的顶点ui1与ui2之间连接m条长为2的路ui1vijui2(i,j=1,2,…,n)得到的图记为m-Fn,4;将孤立顶点w与m-Fn,4的每个顶点连接一条边得到的图记为G,将图G的顶点w加n(m+1)条悬挂边所得到的图记为m-Fn,4+En(m+1).用构造的方法给出图m-Fn,4和m-Fn,4+En(m+1)的优美标号,并证明了m-Fn,4和m-Fn,4+En(m+1)都是优美图.     

对偶图中的H圈与平图的4着色

阐明了对偶图中的H圈与平图的2棵对偶树的相互依存关系,阐述了平图的4着色与2棵对偶树之间的相互依存关系。平图的顶点4着色以及2棵对偶树的分解决定了对偶图中的H圈,对偶图中的H圈也决定了平图的顶点4着色及2棵对偶树的分解。平图H圈决定了对偶图的2棵对偶树的分解及顶点4着色,对偶图的2棵对偶树的分解及对偶图的顶点4着色决定了平图的H圈的分解。2棵对偶树的2着色等价于平图的顶点4着色,内区与外区的分界线恰好是H圈。提出了多面体平图的H圈的构造步骤和多面体平图的顶点4着色步骤。介绍了12面体平图中30个H圈的构造,对偶图中对偶树的分解、以及对偶树的4着色。解决了任意平图中的H圈的分解方法和计数方法,为解决任意平图中的生成树的构造和计数问题奠定了基础。