判断k-可序哈密顿-连通图的新条件

具有n个顶点的图G(n≥3)是k-可序哈密顿-连通的(k是整数,且2≤k≤n),如果对于G中每一个具有k个不同顶点的可序集合S={v1v2,…,vk},都存在G中的哈密顿路P包含S且不改变其中元素的次序.本文证明了:对于具有n个顶点的图G,u、v是G中任意两个不相邻的顶点,且d(u)+d(v)≥n+1.如果G是「k+1/2﹁-连通的k-可序图,k是整数且2≤k≤n/12,则G是k-可序哈密顿-连通图.     

路的k阶幂图的连通性研究

设G是连通图,G的k阶幂图G^k是一个与G具有相同顶点集的图,G^k中的两个顶点相邻当且仅当这两个顶点在G中的距离不大于k.本文研究了路的幂图P_n^k的点连通度κ(P_n^k)、边连通度λ(P_n^k)和限制边连通度λ₂(P_n^k).得到：当n>k时,κ(P_n^k)=λ(P_n^k)=k;关于限制边连通度：当2≤n≤k+1时λ₂(P_n^k)=2n-4,当n>k+1时,λ₂(P_n^k)=2k-1.     

关于图的全荫度和列表全荫度的一些结果

图G的全图T(G)是以V(G)∪E(G)为顶点集的一个图,其中两个顶点相邻当且仅当它们在图G中对应的元素是相邻或关联的.图G的全荫度ρ"(G)是将其全图的顶点集V(T(G))划分为最少的子集数,使得每个子集在全图中的导出子图是一个森林.列表全荫度硝(G)是全荫度概念的列表染色的版本.本文证明了:(1)对完全图‰,ρ"(Kn)=「(n+1)/2];(2)对完全二部图Kn,n,ρ"(Kn,n)=「(n+2)/2];(3)对Halin图G,ρl"(G)≤「(△(G)+2)/2].     

图中具有指定性质的独立4-圈

主要给出了图G恰好含有s个K3和k-s个K4的最小度条件即:设G是一个简单图,s,k是两个正整数且s k,其中G的顶点个数n≥3s+4(k-s)+3,如果G中任意两个不相邻顶点的最小度之和σ2(G)≥4n-3s-8/|2|或者最小度δ(G)≥3n+2k-s-2/4,则G包含k个顶点不相交的圈C1,C2…Ck,并且Ci=K3其中1≤i≤s,Cj=K4其中sj≤k.     

冒泡排序图的超带性

图G的k-路集C(u,v)是连接G中顶点u和v的k条内点不交的路的集合.图G的k-路集C(u,v)是一个k*-路集如果连接顶点u和v的k条内点不交的路包含G中所有的顶点.一个二部图G是k*-带的若G中任意两个属于不同二划分集的顶点之间存在k*-路集.设κ(G)是图G的连通度.一个二部图是超带的若G是i*-带的,1≤i≤κ(G).n维冒泡排序图Bn是二部图,是n-1正则的,有n!个顶点.在本文中,首先证明了Bn是(n-1)*-带的,n≥5,然后得到n维冒泡排序图Bn(n≠3)是超带的.     

有限群的一类新的共轭类图

定义了有限群G的一类新的共轭类图Γ(G):它以G的非中心的共轭类为顶点,不同的顶点xG和yG之间有一条边相连当且仅当它们的代表元的阶有非平凡的公因子.令n(G)和diam(Γ(G))分别表示Γ(G)的连通分支数和直径,证明了对任意有限群G,n(G)≤6和diam(Γ(G))≤6.     

无向de Bruijn图和Kautz图的k元控制

在无向图G中,对于正整数k≥1,图G的一个k元控制集D是顶点集V(G)的一个子集,并且使得G中的每一个顶点至少被D中k个点控制.文章给出了在无向de Bruijn图和Kautz图中最小k元控制集的基数.     

图的强直积的2-距离染色(英文)

设G,H是阶至少为2的简单图。图G与H的强直积是指这样一个图G□×H,其顶点集合为V(G)×V(H),并且(x1,x2)(y1,y2)∈E(G□×H)当且仅当[x1y1∈E(G)且x2y2∈E(H)]或者[x1=y1且x2y2∈E(H)]或者[x2=y2且x1y1∈E(G)]。一个图G的使用了k种颜色的2-距离染色是指一个从V(G)到{1,2,…,k}的映射f,使得任意两个不同的距离最多是2的顶点染不同的颜色。对图G进行2-距离染色所需的最少的颜色数称为图G的2-距离色数,记为χ2(G)。文中将获得两个图的强直积的2-距离色数的可达到的上界和下界:Δ(G□×H)+1≤χ2(G□×H)≤χ2(G).χ2(H)。对一些特殊图,例如Pm□×Kn,Pm□×Wn,Pm□×Sn,Pm□×Fn,Pm□×Cn(n≡0(mod3)或者n=5),给出了它们的2-距离色数。     

关于图的全荫度和列表全荫度的一些结果（英文）

图G的全图T(G)是以V(G)∪E(G)为顶点集的一个图,其中两个顶点相邻当且仅当它们在图G中对应的元素是相邻或关联的.图G的全荫度ρ″(G)是将其全图的顶点集V(T(G))划分为最少的子集数,使得每个子集在全图中的导出子图是一个森林.列表全荫度ρ_l″(G)是全荫度概念的列表染色的版本.本文证明了:(1)对完全图K_n,ρ″K_n=[(n+1)/2];(2)对完全二部图K_n,n,ρ″K_n,n=[(n+2)/2];(3)对Halin图G,ρ_l″(G)≤[(△(G)+2)/2].     

图的圈和路剖分

设G是一个顶点数为n的图,k为任意正整数且k≤n．Hikoe Enomoto和李浩证明了：如果一对不相邻顶点的度和至少为n-k 1,其中k≤n，则除了k=2，G=G5,G能被剖分成k个子图Hi，l≤i≤k，其中Hi是圈或K1或K2．本文中证明了任何一对不相邻顶点的度和至少为n-k，则G能被剖分成k个子图Ki,l≤i≤k，其中Hi是圈或是路．     

Halin图的集染色

对于非平凡连通图G,G的k集染色是指映射c：V（G）→Nk,对任意顶点v∈V（G）,定义邻色集cN（v）={c（u）｜u∈N（v）},若对uv∈E（G）有cN（u）≠cN（v）,则称c为G的一个k集染色.满足上述条件的最小k值称为G的集色数,记为χs（G）.为了更快更有效地给Halin图着色,采用集染色的着色方法,证明了当p≥4时,Halin图G（Cp,Tq）的集色数是3,并且还证明了对任意的Halin图G（Cp,Tq）,有p＋1≤q≤2p-2成立.     

图的独立数与分数一致性

设G是一个顶点集为V（G）,最小度为δ（G）,独立数为α（G）的图, k≥2是整数。图G的支撑子图F称作是图G的分数k-因子,如果对于每一个x∈V（F）都有dhG（x）＝k。如果对于图G的每条边e,图G都有一个分数k-因子包含它而且同时有一个分数k-因子不包含它,则称图G为分数k一致图。证明了如果δ（ G）≥k＋2,且α（ G）≤4k（δ-k-1）（k＋1）2,则图G是一个分数k一致图。     

3-临界图独立数的一个结果

1968年,Vizing提出了关于临界图的独立数猜想：若G是n阶的Δ-临界图,则有α（G）≤n/2.利用Vizing邻接引理研究这一猜想,给出了3-临界图的一个上界.     

关于（g,f）-3-覆盖图

设G是一个图,用V（G）和E（G）表示顶点集和边集,并设g和f是定义在V（G）上的两个非负整数值函数且g〈f。图G的一个（g,f）-因子是G的一个支撑子图F使对任意的x∈V（G）有g（x）≤dF（x）≤f（x）。如果过图G的任何三条边都有一个（g,f）-因子,则称图G是一个（g,f）-3-覆盖图,本文给出了一个图是（g,f）-3-覆盖图的一个充分条件。     

图的Laplacian矩阵谱半径

设G为n阶简单连通图,若L(G)为图G的度对角矩阵与邻接矩阵的差,则称L(G)为图G的Laplacian矩阵.结合非负矩阵谱理论,利用图的顶点度和平均二次度给出了图G的Laplacian矩阵的谱半径的新上界,同时给出了达到上界的极图.     

不含K1＋P3和C4作为导出子图的图的色数

Erodos证明了对于一个图G ,χ（G）-ω（G）可以任意大。因此,对一般图而言,其色数不一定能找到一个与团数有关的上界。文章主要研究了一类 F-free图的色数和团数的关系。得到了如果图G是一个不含K 1＋ P3和C4作为导出子图的图,那么当α（G ）≥3时,χ（G ）＝ω（G ）;当α（G ）＝2时,χ（G ）n ≤2ω（G ）。     

一类整数距离图的点荫度

整数距离图以全体整数作为顶点集，顶点u、υ相邻当且仅当｜u-υ｜∈D，其中D是一个正整数集．对于m〉3，令Dm=[1,m]／[1,3]．本研究得到了G（Dm）的点荫度．     

完全二部图K5，n的点可区别IE-全染色

设G是简单图,图G的一个k-点可区别IE-全染色（简记为k-VDIET染色）f是指一个从V（G）∪E（G）到{1,2,…,k}的映射,且满足：A↓uv∈E（G）,有f（u）≠f（v）;A↓u,v∈V（G）,u≠v,有C（u）≠C（v）,其中C（u）={f（u）}∪{f（uv）｜uv∈E（G）}。数min{k}G有一个k-VDIET染色}称为图G的点可区别IE-全色数,记为χut^ie（G）。本文给出了完全二部图K5,n（n≥6）的点可区别IE-全色数。     

外平面图的平方图的点荫度

图G的平方图G2是以V(G)作为它的点集，两个点在G2中相邻当且仅当它们在G中的距离至多为2.证明了：若G是一个最大度Δ6的外平面图,则G2的点荫度va(G2)=「Δ+12?;特别地，一棵树T的平方图T2的点荫度va(T2)=「Δ+12?.     

关于路核和路剖分的新研究

图G的最长路的阶称为环游阶,记为τ（G）。顶点集V（G）的子集S称为图G的Pn-核,如果满足τ（G[S]）≤n-1且V（G）-S的每一个顶点v都与G[S]中阶为n-1路的端顶点相连。把顶点集V（G）剖分成A,B两部分,使得τ（G[A]）≤a和τ（G[B]）≤b,此剖分称为图G的一个（a,b）-剖分。本文证明了对于n≤3g/2-1的正整数,任意围长为g的图都有一个Pn＋1-核。并且还得到,如果τ（G）=a＋b,其中1≤a≤b,图G的围长g≥2/3（a＋1）,那么G有一个（a,b）-剖分。