关于p3n的优美性

设G(V,E)是一个简单图,对自然数k,当V(Gk)=V(G),E(Gk)=E(G)∪{uv|d(u,v)=k},则称图Gk为k-次方图.本文证明了图P3n的优美性.     

关于图的邻点可区别全染色

提出了图的邻点可区别全染色的概念, 给出了圈、完全图、完全二部图、扇、轮和树的邻点可区别全色数.     

关于图的点荫度

本文研究了外平面图的点荫度和点荫度临界图,得到了外平面图G的点荫度a(G):a(G)={1,若G是树或林;2,若G不是树或林.     

第一类图的若干充分性条件

1964年,V.G.Vizing[2]证明了简单图 G 的边色数 x′(G)满足△(G)≤x′(G)≤△(G)+1.其中△(G)为图 G 的最大度.若x′(G)=△(G),则称 G 为第一类图,并简记为 G∈C~1;若 x′(G)=△(G)+1 则称 G 为第二类图,并简记为 G∈C~2.     

图和补图的全色数

本文用不同于[3]的方法,研究了图及其补图全色数间的关系,得到了其中 p=|V(G)|,G°为 G 的补图。该结果包含了[3]的结果,且当 P 为偶数时更强。§1 引言对于简单图 G=(V,E),使 V∪E 的任何两个相邻或相关联的元素均有不同颜色所需要使用的最少颜色的数目,被称为 G 的全色数,记为 x_T(G)。使用一组颜色着染一个图G 的顶点和边,使得 V∪E 中任意两个相邻或相关联元素均有不同颜色,则称这个着色为     

若干联图的邻点可区别-点边全染色

设G(V,E)是简单图,k是正整数.从V(G)∪E(G)到{1,2,…,k}的映射f被称作G的邻点可区别-点边全染色,当且仅当:■uv∈E(G),f(u)≠f(uv),f(v)≠f(uv),■uv∈E(G),C(u)≠C(v),且称最小的数k为G的邻点可区别-点边全色数.其中C(u)={f(u)}∪{f(uv)|uv∈E(G)},研究了一些联图的邻点可区别-点边全染色法,得到了它们的色数.     

广义Mycielski图的邻强边色数和邻点可区别全色数的两个上界

对简单图G,|V(G)|=p,n是自然数,Mn(G)被称为图G的广义Mycielski图,如果V(Mn(G))={v01,v02,…,v0p;v11,v12,…,v1p;…;vn1,vn2,…,vnp},E(Mn(G))=E(G)∪{vijv(i+1)k|v0jv0k∈E(G),1≤j,k≤p,i=0,1,…,n-1}.文中针对简单图G与它的广义Mycielski图之间的关系,给出了G的广义Mycielski图的邻强边色数和邻点可区别全色数的两个上界.     

关于扇和完全等二部图联图的均匀全色数

对于一个正常的全染色满足各种颜色所染元素(点和边)数量的和相差不超过1时,称为均匀全染色,其所用最少的染色数称为均匀全色数.本文得到了m+1阶扇Fm和完全等二部图Kn,n的联图Fm∨Kn,n的均匀全色数.     

若干图的倍图的均匀邻强边染色

如果图G的一个正常边染色满足相邻点的色集不同,且任意两种颜色所染边数目相差不超过1,则称为均匀邻强边染色,其所用最少染色数称为均匀邻强边色数．本文得到了星、扇和轮的倍图的均匀邻强边色数．     

关于图的带宽

图的带宽在计算方法上有重要的应用。已经证明,确定图的带宽属于 NP—完全问题。最近,我国图论工作者先后解决了 Dewdney 在一九七六年作的关于图的带宽的一篇综合报告中提出的三个问题,使带宽问题的研究推进了一步[3].[4].[5].[6].。