完全多部图Kn(t)的G-分解

如果Kn(t)能分解成一族同构于G的边不交的子图的集合,那么称Kn(t)存在G 分解.本文讨论了当G是有一条悬边的三长路时,Kn(t)的G 分解的存在性并给出该分解存在的充要条件.     

非连通并图的优美标号研究

设图G3是长度为3的圈C3或为含3个顶点的路P3,文章给出了非连通图(G3∨Km)∪Kn,t和(G3∨Km)∪Pn,并证明了对任意正整数m,n,t,如果min{n,t}≤m,则图(G3∨Km)∪Kn,t是优美图;如果2≤n≤2m+1,则图(G3∨Km)∪Pn是优美图;同时证明了对任意正整数m,n,图(G3∨Km)∪St(n)和(G3∨Km)∪W2n+5是优美图.其中,Pn是n个顶点的路,G1∨G2是图G1与G2的联图,Km是m个顶点的完全图,m是Km的补图,Kn,t是具有二分类(X,Y)的完全偶图,且|X|=n,|Y|=t,St(n)是具有n+1个顶点的星形树,Wn是具有n+1个顶点的轮图.     

一类图的多重多部图设计的存在性

λKn(g)是一个λ重完全n部图,G为一个不带孤立点的简单图.一个(λKn(g),G)-设计是将λKn(g)划分成边互不相交的子图,使得每一个子图都和G同构.对一个五点六边图G的λ重多部图设计的存在性问题进行了研究,证明了(λKn(g),G)-设计存在的充要条件是λn(n-1)g2≡0(mod12),n≥3且ng≥5.     

由圈长分布确定的偶图的几个定理

阶为n的图G的圈长分布是序列(c1，c2，…，cn)，其中ci是图G中长为i的圈数，得到如下结果：(1)设A包含于E(Kn，n)，则当Kn，n[A]≌K1，j或Kn，n[A]≌K2时，Kn，n－A是由它的圈长分布确定；(2)设A包含于E(Kn，n，|A|=4，n≥11，则Kn，n－A是由它的圈长分布确定的。     

关于完全多部图Kn(t)的{C3,C4,C5}-强制分解

Kn(t)的{Ci，Cj,Ck}-强制分解是指将Kn(t)分解为长为i或j或k的圈，并且分解中至少有一个长为i．j和k的圈．本文证明了多部图Kn(t)的{C3，C4，C5)-强制分解存在的必要条件也是充分的。     

一个五点六边图的多部图设计

Kn(g)是一个完全n部图,G为一个不带孤立点的简单图.一个(Kn(g),G)-设计是将Kn(g)划分成边互不相交的子图,使得每一个子图都和G同构.本文讨论了一个五点六边图G的多部图设计存在性问题,证明了(Kn(g),G)-设计存在的充要条件是n(n-1)g2≡0(mod12)且ng≥5.     

关于完全多部图Kn(t)的{C3,C5}-强制分解

关于完全多部图Kn(t)的Ck 分解 ,已经取得了一系列的研究成果。Kn(t)的 {Ci,Cj} 强制分解则是指Kn(t)分解为长为i或j的圈 ,并且分解中至少各有一个长分别为i和j的圈。本文证明了多部图Kn(t)的 {C3,C5 } 强制分解存在的必要条件也是充分的。     

偶图Kn,n+8-A(│A│≤3)的圈长分布唯一性

阶为n的图G的圈长分布是序列(c1,c2,…,cn),其中ci是图G中长为i的圈数.设A(∈)E(Kn,n+8),在情况①G=Kn,n+8(n≥13);②G=Kn,n+8-A(│A│=1,n≥15);③G=Kn,n+8-A(│A│=2,n≥17);④G=Kn,n+8-A(│A│=3,n≥19)时,图G由其圈长分布唯一确定.     

非连通图（P3∨■）∪G及（C3∨■）∪G的优美性

将k-优美图的概念进行了推广,引入A～B优美图的概念,并以此为基础,得到了非连通图(P3∨■)∪G及(C3∨■)∪G是优美图的一个充分条件。证明了对任意正整数k,m,n,t,当k≤n≤t,n+k-1≤m时,图(P3∨■)∪(∪kj=1Kn,t)和(C3∨■)∪(∪kj=1Kn,t)是优美图;当k=1,2,2≤n<2m+1时,图(P3∨■)∪∪kj=1P(j)n,(C3∨■)∪∪kj=1P(j)n和(P3∨■)∪Pn∪St(t)是优美图;当2≤n≤2m+1时,(C3∨■)∪Pn∪St(t)是优美图。本文的结果推广了现有的一些结论。     

非连通图(P3∨(Km))∪G及(C3∨(Km))∪G的优美性

将k-优美图的概念进行了推广,引入A～B优美图的概念,并以此为基础,得到了非连通图(P3∨(Km))∪G及(C3∨(Km))∪G是优美图的一个充分条件.证明了对任意正整数k,m,n,t,当k≤n≤t,n+k-1≤m时,图(P3∨(Km))∪(k∪j=1Kn,t)和(C3∨(Km))∪(k∪j=1Kn,t)是优美图;当k=1,2,2≤n＜2m+1时,图(P3∨(Km))∪k∪j=1P(j)n,(C3∨(Km))∪k∪j=1P(j)n和(P3∨(Km))∪Pn∪St(t)是优美图;当2≤n≤2m +1时,(C3∨(Km))∪Pn∪St(t)是优美图.本文的结果推广了现有的一些结论.     

步长为1和n/2循环图的导出匹配可扩性研究

如果一个图的任何一个导出匹配都能包含在一个完美匹配当中,就称之为导出匹配可扩的.对有2n个顶点x1,x2,…,x2n的图,如果对于i-j≡±1(mod2n)或者i-j≡±n2(mod2n)的i和j,均有xixj∈E(G),则称其为步长为1和n2的循环图,记为C2n(1,2n).本文的主要结论为:C2n(1,2n),n#4,是导出匹配可扩的.     

循环图中部分图类的导出匹配可扩性

如果一个图的任何一个导出匹配都能包含在一个完美匹配当中,就称之为导出匹配可扩的.对有2n个顶点x1,x2,…,x2n的图,如果对于i-j≡±1(mod2n)或者i-j≡±k(mod2n)的i和j,均有xixj∈E(G,)则称其为步长为1和k的循环图,记为C2n(1,k.)通过详细讨论循环图的导出匹配可扩性,具体给出了循环图中的部分图类的导出匹配可扩性。     

关于K_n-{v_(n-5)v_(n-4),v_(n-3)v_(n-2),v_(n-1)v_n}(n≥14,n≡0(mod2))的点可区别边色数

给出了图K_n-{v_(n-5)v_(n-4),v_(n-3)v_(n-2),v_(n-1)v_n}(n≥14,n≡0(mod2))的点可区别边色数,其中Kn为n阶完全图。     

若干点不交的n阶路的并图的非正规强度

图 G 的一个 m-边赋权 w 是指从 E（G）到｛1，2，…，m｝的一个映射。对任意 e∈E（G），称 w（e）为边 e 在 w 下的权。 w 称为是 m-非正规分配，如果对 G 的任意两个不同的点 u 和 v，与 u 关联的边的权之和异于与 v 关联的边的权之和。使得 G 具有 m-非正规分配的最小正整数 m 叫 G 的非正规强度。基于这一理论，利用构造矩阵的方法，研究了若干点不交的 n 阶路的并图（n≡2（mod 4）和 n≡3（mod 4））的非正规强度。     

关于Kn-{vn-5vn-4,vn-3vn-2,vn-1vn}（n≥14,n≡0（mod2））的点可区别边色数

给出了图KKn-{vn-5vn-4,vn-3vn-2,vn-1vn}（n≥14,n≡0（mod2））的点可区别边色数,其中Kn为n阶完全图。     

舵轮图Hn的k-边优美指标集

讨论了舵轮图 Hn的边优美指标集问题。对 n≡0,1,2,3,5mod6,完全确定了它的边优美指标集;对 n≡4 mod 6,给出了它的一类边优美标号。     

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

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

若干广义Petersen图的邻点可区别全染色

研究了若干广义Petersen图G(n,r)的邻点可区别全染色。 构造性地证明了:若n≡0(mod 4),r0(mod 4)或n≡0(mod 5),r0(mod 5),则G(n,r)的邻点可区别全色数为5。     

平面图线性2-荫度的一个上界

设图G为最大度为Δ的平面图。图G的线性2-荫度是将图G的边集合分解成k个线性森林的最小整数k,其中每个分支树为长至多为2的路,记为la2（G）。得到了平面图线性2-荫度的上界：若Δ≡0,3（mod 4）,则la2（G）≤「Δ/2棢＋8;若Δ≡1,2（mod 4）,则la2（G）≤「Δ/2棢＋7。