若干积图的点可区别边染色

证明了:(1)两个n(n2)阶完全图的积图的点可区别边色数为2n. (2)对阶至少是3的完全图Kn,若χ′vd(G)=Δ(G),则χ′vd(G×Kn)=n+Δ(G).(3)若χ′vd(Gi)=Δ(Gi),i=1,2,则χ′vd(G1×G2)=Δ(G1)+Δ(G2).     

一些笛卡尔乘积图的限制连通度

子集S(∩)V(G)称为限制割,若任何点v∈V(G)的邻点集NG(v)都不是S的子集且G-S不连通.若G中存在限制割,则定义限制连通度κ1(G)=min{| S|S是G的一个限制割}.考虑了笛卡尔乘积图,证明了设G=G1×G2×…×Gn,若Gi是满足某些给定条件的ki连通ki正则且围长至少为5的图,其中i=1,2,…,n,则κ1(G)=2n∑i=1ki-2.     

若干多重联图的边染色

设G1,G2,…,Gn是n个(n≥2)两两不相交的简单图,它们的n-重联图是在G1 G2 … Gn中,将Gi的每一顶点与Gj的每一顶点连接起来(i≠j,i,j=1,2,…,n)所得到的图,简记为K(G1,G2,…,Gn).若Gi≌G,i=1,2,…,n,则称K(G1,G2,…,Gn)为G的等n-重联图,简记为K(n,G).本文研究了若干多重联图的边染色.     

特征标维数图是一种连通图的可解群的注记

假设群G可解,且特征标维数图Γ(G)的顶点集ρ(G)=π1Uπ2U{p},其中｜π1｜,｜π2｜≥1,π1∩π2=φ,且π1与π2中顶点不相邻,本文证明了G的Fitting高2≤n(G)≤4,且若n(G)≠4,则存在长最多为6的正规子群列G=G0(△)G1(△)…(△)Gs使商群Gi/Gi+1或者是交换群或者是p-群.     

图的直积和字典积的Laplacian谱和Kirchhoff指数

由图G1、G2的Laplacian谱得到了它们的直积G1×G2和字典积G1[G2]的Laplacian谱,并计算了R(G1×G2)和R(G1[G2]).     

半CAP-子群与有限群的性质

设G是有限群,G的子群H称为G的半CAP-子群,如果存在G的一个主群列1 =G0△←G1 …△←Gn-1△←Gn=G使得H覆盖或者避开Gi/Gi-1,其中i=1,2,…,n.本文主要讨论极小子群和4阶循环子群的半覆盖-避开性对有限群结构的影响.     

链状割点图的Hosoya多项式

任一连通图的Hosoya多项式的定义如下:H(G)≡H(G,x):=∑d(G,k)xk k≥0,其中d(G,k)是图G中距离为k的点对的个数。事实上,d(G,0)等于图G的点数,而d(G,k)等于图G的边数。设{Gi}ni=1是一个两两不交的图的集合,并且Vi,Vi∈V(Gi),所谓链图C(G1,G2,…,Gn)≡C(G1,G2,…Gn;v1,w1,v2,w2,…,vn,wn)指的是将各点对wi和vi+1粘合起来而得到的图,其中i=1,2,…,n-1。文章得到了链状割点图的Hosoya多项式,并且,作为引理,并给出了树的Hosoya多项式。     

拟-morphic群的一些性质

定义了强拟-morphic群,给出拟-morphic群与强拟-morphic群的一些刻画,并考察了拟-morphic群的直积封闭的充要条件:即设G=G1×G2×…×Gn,若i≠j时,hom(Gi,Gj)={θ},则G是拟-morphic群当且仅当Gi(i=1,2,…,n)是拟-morphic群.最后讨论了拟-morphic交换群,指出拟-morphic可除群与拟-morphic无扭群是等价的,并得到了扭群的拟-morphic性的刻画.     

强乘积图的连通度

用k1＞0和δi表示图Gi(i=1,2)的连通度和最小度,给出了无向图强乘积的连通度一个下界κ(G1(□×)G2)≥min{κ1(1+δ2),k2(1+δ1)}.     

某些笛卡尔乘积图的超边连通度

一个连通图称为超边连通的,如果去掉每一个最小边割集后产生一个孤立点。一个超边连通图的超边连通度λ′(G)是指那些去掉后不产生孤立点的边割集的最小基数。考虑笛卡尔乘积图并证明:若对于每一个i=1,2,…,n,Gi是ki(≥1)正则,ki连通图且满足某些给定的条件,则λ′(G1×G2×…×Gn)=2∑from i=1 to n(ki-2)。     

图的点可区别星边色数的一个上界

图\,$G$\,的点可区别星边边色数, 记为\,$\chi'_{\rm vds}{(G)}$, 是图\,$G$\,的点可区别星边染色所用色的最小数目. 得到了一些特殊图的星边染色,
并证明了若图\,$G$\,是一个最小度不小于\,5, 且顶点数不超过\,$\Delta^7$\,的图时, $\chi'_{\rm vds}{(G)}\leqslant {14\Delta^{2}}$, 其中\,$\Delta$\,是图\,$G$\,的最大度.     

图的点可区别无圈边色数的一个上界(英文)

图G的一个正常边染色f,若满足:1)G中无2-色圈;2)对于V(G)中的任意两点u和v,有C(u)≠C(v),这里C(u)={f(uw)|uw∈E(G)},则f叫做图G的一个点可区别无圈边染色.图G的点可区别无圈边色数,记为χ′_(vda)(G),是图G的一个点可区别无圈边染色所用色的最小数目.证明了若图G是一个最小度不小于5,且顶点数不超过30Δ~4的图时,χ′_(vda)(G)≤10Δ~2,其中Δ是图G的最大度.     

一类广义Petersen图的邻强边染色

研究了一类广义Petersen图G(n,k)的邻强边染色,构造性地证明了:若n≡0(mod3),k≡/0(mod3),则χ_(as)~′(G(n,k))=4.其中χa′s(G(n,k))表示G(n,k)的邻强边色数.     

关于着色参数Nordhaus－Gaddum问题的若干注记

分别以Ｘ（Ｇ）、Ｘ１（Ｇ）、Ｘ２（Ｇ）记图Ｇ之色数、边色数和金色数，对任意Ｐ阶图Ｇ及其补图，当Ｘ１（Ｇ）、Ｘ１（Ｇ）不为零时，本文得到下面三个Ｎｏｒｄｈａｕｓ－Ｇａｄｄｕｍ型乘积的下界：对于每一工整数Ｐ，这三个下界均可达到。     

广义Mycielski图的边色数

设μ1(G)表示一个图G的Mycielski图.广义Mycielski图μm(G)是Mycielski图μ1(G)的自然推广.研究广义Mycielski图μm(G)的边染色问题,运用换色技巧证明了:若G是不同于K2的连通简单图,则对任何m≥2,μm(G)是第一类的,即边色数等于最大度.推广了现有关于Mycielski图的边色数的相关结果.     

合成图的点可区别正常边色数

通过将图G和H的合成图G［H］分解成一个直积图G□H和一个二分图Z的边不交并的方法, 得到了χ′_s(G［H］)≤χ′_s(G□H)+χ′(Z),其中χ′_s(G)表示G的点可区别正常边色数.     

平面图的强边染色的一个结果

如果图G的一个正常边染色的任意有公共邻边的两条边的染色不相同,则它是图G的一个强边染色。图G的强边染色所需要的最小颜色数称作图G的强边色数。本文利用差值转移方法证明了最大顶点度为偶数且不小于6的平面图,如果其不含有3圈,则其强边色数不超过5△2/4,特别地,本文证明了最大顶点度为4的平面图,如果其围长不小于5,则其强边色数不超过20。     

不含三角形的平面图的无圈边染色

图的无圈边染色是图的染色理论中的一个重要问题.2001年,Alon等猜想任意简单图G的无圈边色数都不超过Δ(G)+2,其中Δ(G)为图G的最大顶点度.为了深入研究该猜想对平面图是否成立,利用差值转移方法并结合最小反例图的一些结构性质,证明了:不包含三角形的平面图G,如果其最大顶点度不小于6,则其无圈边色数不超过Δ(G)+3.     

图mP2∪mCt（3≤t≤10）的点可区别正常边染色

图G的正常边染色称为是点可区别的,如果对G的任意两个不同的顶点u,v,与u关联的边的颜色构成的集合异于与v关联的边的颜色构成的集合.对图G进行点可区别正常边染色所需要的最少颜色数称为是G的点可区别正常边色数,记为χ′s(G).通过将路和圈填装到完全图,我们给出了mP2∪mCt的点可区别正常边色数的一个刻画,并利用递归染色的方式,得到了χ′s(mP2∪mCt)(3≤t≤10).     

含相邻三角形的平面图的列表边和列表全染色

给定一个平面图G,χ´_l(G)和χ"_l(G)分别表示图G的列表边色数和列表全色数.证明了:如果一个平面图G满足Δ(G)≥7,并且任何一个三角形至多和一个其他的三角形相邻,则有χ´_l(G)≤Δ(G)+1和χ"_l(G)≤Δ(G)+2成立。