多部图λkn(g)的G-设计,G为有1条悬边的4长圈

设λkn(g)是一个λ重完全n部图,G为一个不带孤立点的简单图,一个(λkn(g),G)-设计是将λkn(g)划分成边互不相交的子图,使得每一个子图都和G同构.在此基础上讨论了G为有1条悬边4长圈时多重完全多部图的G-设计的存在性,并给出其存在谱.     

一类六点八边图的图设计

设Kv是一个v个点的完全图，G为Kv的一个不含孤立点的简单子图．Kv的一个G-设计，常记为（v，G，I）-GD，是指一个二元组（X，B），其中x为Kv的顶点集，B是Kv的一些子图（亦称为区组）构成的集合，使得每一个区组与G同构，且Kv的任何一条边恰在B的一个区组中出现．文章讨论了一类六点八边图中尚未解决的3个图G（i=1，2，3）的图设计存在性问题，并证明了（v,Gi，1）-GD（i=1，2，3）存在的必要条件v=0，1（mod16）且v≥16也是充分的．从而给出了这类六点八边图图设计存在的完全解．     

n阶q-树的三次整子图色性的注记(下)

Chao等,韩伯棠和Thomas Wanner分别仅用色多项式表征了q-树和q-树的(一次)整子图;刘象武等又表征了当最小度Δ(G)≠q-3时,q-树的二次整子图的色性．本文证明了n阶q-树的三次整子图G的色多项式为：P(G;λ)=λ(λ-1)…(λ-q 1)^4(λ-q)^n-q-3且G为q 1色图,色分划数为8;反之,在G的一个q 1着色下,若恰有一个二色子图不连通,则G是n阶q-树的三次整子图。     

一类图中具有最小能量的图

设λ1,λ2,…,λn是图G的特征值,则称E(G)=|λ1| |λ2| … |λn|为图G的能量.用Sl1n,l2表示由两个具有唯一公共顶点u的圈Cl1和Cl2,且其余边均为u上的悬挂边的n阶双圈图.利用Sachs子图证明了在所有含有两个边不相交的圈Cl1和Cl2的n阶双圈连通图中Sl1n,l2是能量最小的.     

n阶q-树的三次整子图色性的注记(上)

Chao等,韩伯棠和Thomas Wanner分别仅用色多项式表征了q-树和q-树的(一次)整子图;刘象武等又在参考文献中表征了当最小度δ(G)≠q-3时,q-树的二次整子图的色性。本文证明了n阶q-树的三次整子图G的色多项式为：P(G;λ)=λ(λ-1)…(λ-q 1)^4(λ-q)^n-q-3且G为q 1色图,色分划数为8;反之,在G的一个q 1着色下,若恰有一个二色子图不连通,则G是n阶q-树的三次整子图。     

关于柱图Cλ(Pn)的细分图的k-优美性

一个简单图G=(V,E)是k-优美的(k≥1为整数),如果存在单射f:V(G)→{0,1,2,…,｜E｜+k-1}使得对所有的边uv∈E(G),由f*(uv)=｜f(u)-f(v)｜导出的映射f*:E(G)→{k,k+1,…,｜E｜+k-1}是双射.若G是简单图,且在G的所有相邻的两个顶点之间都加入一个顶点,则所得到的图称为G的细分图,该文证明了当λ≥2,n≡0(mod2)时,Cλ(Pn)的细分图Cλ(Pn)是k-优美图.     

Gallai图中的圈与完全k部图（英文）

设G是一个E(G)非空的图。图G的Gallai图Gal(G)是把G的边集作为它的点集,若G中的两条边e和f相邻但不在同一个三角形中,则Gal(G)中的两个不同顶点e和f相邻。显然,图G的Gallai图Gal(G)是线图L(G)的一个生成子图。本文刻画Gallai图分别是圈和完全k-部图的原图。     

二分图上有限制条件的（g，f）-因子分解

设G=（X,Y,E）是二分图,g,f是定义在V（G）上的正整数值函数,且对任意的x∈V（G）有g（x）〈f（x）。令G是（mg,mf-1）-图,证明了：①若,g（x）≥1,H是G的任一含有m条边的子图。则G有一个（g,f）-因子分解与H-正交。②若g（x）≥2,H是G的任一含有2m条边的子图,则G有一个（g,f）-因子分解与H2-正交。     

恰有两个主特征值的三圈图

设G＝(V,E)是简单连通图,V,E分别是图的顶点集与边集.若图G的邻接矩阵A(G)的特征值λ存在一个各分量之和不为零的特征向量,则称λ为图G的主特征值.恰有k(k≥2)个主特征值的图的刻画是图谱理论中一个未解决的公开问题.利用恰有两个主特征值的一个充要条件刻画了恰有两个主特征值的三圈图,它们有无限多个,但只具有48个...     

具SR性质的基本双圈图

设图G邻接矩阵为A(G)的每一特征值λ的倒数1/λ也是A(G)的特征值,则称C具有R性质;而且,若λ的重数与1/λ的重数也相等,则称C具有SR性质,证明了具SR性质的基本双圈图只有一个图.     

一类Cayley图的边Hamilton性

设G为有限群,|G|=p3,p为素数,M是G的一个生成集.证明了p3阶的Cayley图X(G,M)是边-Hamilton图.     

关于极大二部匹配可扩图

若简单图G的每一个二部匹配都可增扩为G的一个完美匹配,则称图G是二部匹配可扩图(简称BM-可扩图)。BM-可扩图广泛地存在于相对稠密的图类之中。讨论树梯图、加强树梯图和正则加强树梯图等图类,并在树梯图图类中确定了正则加强树梯图是加强树梯图中的极大BM-可扩图的刻画。该结论与Wang Xiu-mei一起给出了三类极大BM-可扩图的完全刻画。     

图的最大度与（p,1）-全标号

图G的一个(p,1)全标号是与频道分配有关的一种染色,它是从V(G)UE(G)到一个整数集合的映射,且满足:1)图G的任意两个相邻的顶点得到不同的整数;2)图G的任意两个相邻的边得到不同的整数;3)图G的任意一个顶点和它所关联的边得到的整数必须至少相差P.一个(p,1)一全标号的跨度是指最大标号数与最小标号数的差.图G的所有(P,1)-全标号函数中最小的跨度,称为图G的(p,1)-全标号数,记为λTP(G).本文我们证明了对任意的图G,其最大度△是偶的且至少是10,则λT2≤2△-1.另外对于任意的简单连通图G,其最大度为△,如果G的最大度点的邻点中至多有△-1个最大度点,则λTP(G)≤p+4.     

关于Mbius梯的细分图的k-优美性

一个简单图G =(V ,E)是k 优美的 (k≥ 1为整数 ) ,如果存在单射f:　V(G)→ { 0 ,1,2 ,… ,|E| +k - 1}使得对所有的边uv∈E(G) ,由f (uv) =|f(u) -f(v) |导出的映射f :　E(G)→ {k ,k + 1,… ,|E| +k - 1}是双射 .设G是简单图 ,在G的每相邻两顶点之间都加入一个顶点后所得到的图称为G的细分图文章证明了M bius梯的细分图是k 优美图     

17阶强正则自补图的唯一性

本文不使用“块次矩阵”的方法,获得一个强正则图是17阶强正则自补图的充要条件:1)p=17,k=8,λ=3,=4;2)对于u∈V(G),u的邻点导出子图为8阶3度正则图,且u的不邻点导出子图为8阶4度的正则图.由此证明17阶强正则自补图是唯一的,从而将文献[2]中的结论k≥4改进为k≥6.     

一类广义树的色性

本文证明了图G是树序列为{1，p，1，q-4个…1，2，2，r}的广义树的充要条件是G的色多项式为P(G；λ)=λ(λ-1)^p(λ-2)…(λ-q 2)^2(λ-q 1)^2(λ-q)^r，这里q=4.5。     

零度为1的无交双圈图刻划

含有n个顶点,n＋1条边的简单连通图称为双圈图．若双圈图G中存在的两个圈,它们不舍懿共交点,则称G是无交双圈图．图的零度是指在图的谱中0特征值的重敷．本文刻划了零度为1的所有元交双圈图的集合．     

折叠超立方体的边邻域连通度

折叠超立方体是最受关注的网络模型之一．设e是图G的一条边，如果从图G中删掉以e为中心的双星子图，则称e“倒戈”．设S为一个边集，如果S中的边全部倒戈，若剩下的子图或者不连通，或者是一个孤立点，或者是空集，则称S为G的割边策略．G的最小割边策略所含的边数为边邻域连通度．该文主要证明了折叠超立方体FQn的边邻域连通度为n．     

图中存在f-因子的度条件

设n≥3是一个整数，G是一个具有顶点集V(G)的图．并设，是定义在V(G)上的非负整值函数．设a=mx|g(x)|x∈V(G)|，b=min|f(x)|x∈V(G)|，并有b，a≥2，n≥b／(a-1) 1，如果存在点v∈V(G)使得f(v)m|(mod 2)，假定b≥n-1．则每个连通的使得f(V(G))为偶数的K1,a-free图G有f-因子，如果它的最小度至少是((n-1)(b 1) a)/a)[b(n-1) a/2(n-1)] [(n-1)/a]([b(n-1) a/2(n-1)])^2 n-3.     

关于M(o)bius梯的细分图的к-优美性

一个简单图G=(V,E)是к-优美的(k≥1为整数),如果存在单射 fV(G)→{0,1,2,…,| E|+k-1}使得对所有的边uv∈E(G),由f*(uv)=|∫(u)-f(v)|导出的映射 f*E(G)→{k,k+1,…,|E|+k-1}是双射.设G是简单图,在G的每相邻两顶点之间都加入一个顶点后所得到的图称为G的细分图.文章证明了Mobius梯的细分图是к-优美图.