关于笛卡儿积1—因子分解的进一步结果

设G为无桥三次图,文[1]证明了G×K_3存在1-因子分解的充分条件。通过引入“圈图”概念,给出了G×K_3存在1-因子分解的判别法则。本文给出笛卡儿积1-因子分解的进一步结论和判则。 关于无桥三次图G和K_3的笛卡儿积G×K_3的1-因子分解,已有结论如次。 (Ⅰ)若G有一个同构于E×K_3的子图H(E表示单一的一条边),G_1是图G中H代之以H_1=P_(2k+1)×K_3得到的新图(P_(2k+1)表示长(2h+1)的路)。假定G的边被t种颜色如此着色:t≥5,H的侧面边的颜色取自{1,2,3,4}。则G_1的边能够这样着色:H_1的端面边和所有不在H_1中的边按G中着色,H_1侧面边和H_1内部三角形的边仅用颜色{1,2,3,4}着色。([1]引理2)。     

图有生成闭迹的充分条件

设 G 是一个简单图,(?)e=uv∈E(G),定义 e 的度 d(e)=dCu)+d(v),其中 d(u)和 d(v)分别为 u 和 v 的度数.本文得到了如下两个结果:1) 设 G 是 p≥3阶简单连通无桥图,G 不含 C_3和 C_4,若对 G 中任何相距为2的两边 e_0及 e_1,d(e_0) +d(e_1) ≥p+1,则 G 有一个生成闭迹.2) 设 G 是 P≥3阶简单连通无桥图,G 不含 C_3和 C_4若对任何相距为1两边 e_0及 e_1,d(e_0) +d(e_1) ≥p+2则 G 有一个生成闭迹.     

p(n,k)×k_3的1-因子分解

图G和H的笛卡儿积G×H定义如次: (i)选取H的一种标号; (ii)在G的拷贝中,每一顶点用H的一个拷贝代替; (iii)G的每一边用连结(该边端点)对应的H的两个拷贝的相同标号顶点的边集代替。 换言之,如果V(G)={a_1,a_2,…,a_g},V(H)={b_1,b_2,…,b_h},则V(G×H)=V(G)×V(H),而(a_i,b_j)adj(a_k,b_1)当且仅当a_i adj a_k且b_j=b_1     

混合Ramsey数X_2(m,k_(1,n))的下界

一个图G的全色数x_2(G)是着色G的边和顶点使相邻、关联元素均着不同色所需要的最少颜色数。对于正整数m和星形图K_(1,n),混合Ramsey数x_2(m,K_(1,n))是这样的最小正整数P,使得任一P阶图G或者有x_2(G)≥m,或者G的补图G含K_(1,n)为子图。本文引进全着色矩阵的概念,据此得到混合Ramsey数x_2(m,K_(1,n))的下界:对于m≥3、n≥1,有 x_2(m,K_(1,n))≥m+n-2。 结合Fink给出的上界可知,当m奇数、n偶数时,x_2(m,K_(1,n))=m+n-2;其余情况时,m+n-2≤x_2(m,K_(1,n))≤m+n-1。     

边赋权简单图最长圈问题研究

最长圈问题是图论中重要的研究课题,它起源于汉密尔顿圈问题。边赋权图是边上赋正值的图。边赋权图的最长圈,是指所有边权值之和最大的圈。图论中有个著名猜想,即2连通弦图所有最长圈都经过同1个顶点。该猜想与边赋权区间图的最长圈问题紧密相关。研究了边赋权简单图(即只有2个极大团的图)的最长圈问题,并证明了该图上所有最长圈经过同1个顶点。     

正则k-覆盖图

图G的k-正则生成子图称为G的一个k-因子,若图G的每条边都含于G的一个k-因子中,称图G足k-覆盖的。对任意给定的正整数γ、λ和k(λ≥2),基于文[1,2]的已知结论,本文给出了所有γ-正则λ-边连通图是k-覆盖图的充分必要条件。     

含完全子图K_m的几个结论

本文给出了图G含完全子图K_m的一个充分条件:G有n个顶点,f(n,m)=[((m-2)n~2)/(2(m-1))]+1条边。并通过构造完全m-1部图T及其边数S(n,m)的计算,证得当n=0,±1,±2(mod(m-1))时或3≤m≤8时,上述结论中的f(n,m)是最好的。     

两类广义字典积S_n[h_n]的点可区别边染色

研究了广义字典积G[h n]中G为n(n≥3)阶星Sn且与Sn最大度顶点对应的Hn-1分别为空图和完全图时的点可区别边染色.利用构造边染色的方法,得到了这两类广义字典积图的点可区别边色数.     

一类图的点圈扩张性

本文的主要结果是：设G是2-连通图．若，则G的每个点v都在3-圈或4-圈或5-圈上，并可由此出发经过若干次1或2-扩张，最后得到Hamilton圈．     

K_(2n)完美1-因子分解的一些结果

K_(2n)的1-因子分解称为完美的,如果它的任意两个不同的1-因子的并形成K_(2n)的Hamilton圈.1963年,A.Kotzig猜想是:n≥2时,K_(2n)有完美1-因子分解,该猜想已成为图论和组合设计中最难的未解决的问题之一。本文利用有限城上的强初子和计算机构造了K_(12168)和K_(16808)的完美1-因子分解。     

关于完全t部图的色等价性

设K（n1,n2,…,nt）表示完全t部图,K(n1,n2,…,nt）－A表示从K（n1,n2,…,nt）中删去子边集A所得之图．本文证明了：令G＝K（n1,n2,…,nt）,J为整数集,R为实数集．设简单图Y满足Y～G,则且进一步有：若s＞0且αi∈R（i＝1,2…．t）．则     

一类Hamilton无爪图

对任一2-连通无爪图G,如果存在v_0∈V(G),|N(v_0)|=|V(G)|-1,则对任意两个顶点a,b∈N(v_0),G中存在以a,b为其端点的Hamilton路.并由此证明了2-连通且局部连通的无爪图是Hanilton图.     

一类特殊图的连通度与边连通度之间的关系

本文对一类特殊图——k—正则图给出了连通度与边连通度之间的定量关系:K＇≤[k/2]K。并通过证明过程把这种关系又进一步推广到更为一般的图类上去.对一个简单图G,若存在K个其度不超过k的顶点构成图G的一个点割集,则也有关系式K＇≤[k/2]K成立.由此,对任意一个简单图G,都有关系式K＇≤[△/2]K成立,从而文献[1]中的习题3.1.6(若G是3—正则简单图,则K=K＇)便成为本文的一个自然推论.     

非H-无爪图最长圈的若干性质

设G是2-连通无爪图,C是G的最长圈,R=G-C非空.证明了C满足以下5个性质;1)不存在c∈Nc(R),使G[N(c)]连通;2)不存在c∈Nc(R)和y∈V(G)(y≠c),使G[N(c)U{y}]连通且|N(y)∩N(c)|≥3;3)不存在c∈Nc(R)和y∈V(G),使G[N(c)∪{y}连通且G[N(y)]连通;4)不存在c∈Nc(R)和y∈K_1,使|N(y)∩(N(K_2)-{c}|≥2(其中K_1是G[N(c)]的含c~+,c~-的一个分支,K_2是另一个分支);5)不存在c∈Nc(R)和y∈V(G),使|N(y)∩K_1|≥2且有连接K_2与y的路P满足:对P的任一中途点u,或u∈V(C)或u~+u~-∈E(G).     

积图P_2×C_6的邻点可区别全染色

设G是阶数不小于3的简单连通图,G的k-正常全染色σ称为是邻点可区别的,如果对G的任意相邻的两顶点,其点的颜色及关联边的颜色构成的集合不同,这样的k中最小者称为是G的邻点可区别全色数．得到了P_2×C_6的邻点可区别全色数．     

高度不正则图的全着色

图Ｇ的正常ｋ全着色是指用ｋ种颜色对Ｇ的点和边着色，使相邻或相关联的元素（点或边）着不同色。其中最小的ｋ称为Ｇ的全色数，记为χＴ（Ｇ）。设Ｇ是一个简单图，υ是Ｇ的任意一个顶点，若与υ相邻的顶点的度互不相同，则称Ｇ为高度不正则图。对高度不正则图Ｇ，文中证明了χＴ（Ｇ）＝Δ（Ｇ）＋１，同时也给出了着色的算法，其中Δ（Ｇ）为Ｇ的最大度数且Δ（Ｇ）≥２。     

积图P2×C6的邻点可区别全染色

设G是阶数不小于3的简单连通图,G的k-正常全染色σ称为是邻点可区别的,如果对G的任意相邻的两顶点,其点的颜色及关联边的颜色构成的集合不同,这样的k中最小者称为是G的邻点可区别全色数.得到了P2×C6的邻点可区别全色数.     

完全二部图的拟C_(2k)-因子分解

λKm,n表示完全二部多重图,kC2表示2k长圈。如果λKm,n的子图F包含λKm,n的m+n-1个点,且其每个分支都同构于kC2,则称F为λKm,n的拟kC2-因子。如果λKm,n的边集可以划分为λKm,n的拟kC2-因子的和,则称λKm,n存在拟kC2-因子分解。本文利用直接构造法,得到完全二部多重图λKm,n存在拟kC2-因子分解的充分必要条件是:(1)λ=0(mod 2),(2)m=n+1,(3)n=0(mod k)。     

路和圈的弱直积图的星边色数

若图G的一个正常染色使得G中没有长为4的路是2-边染色的,则称此染色是G的一个星边染色,使得图G有星边染色的最小颜色数为星边色数,记作x′s(G).文章给出了路和圈的弱直积图的星边色数:对于图Pm×Cn(m≥2,n≥3)的星边色数分以下三种情形:x′s(P2×Cn)=3(n≥3);5≤x′s(Pm×Cn)≤6(m=3,4;n≥3);6≤x′s(Pm×Cn)≤8(m≥5,n≥3).     

可换群的结构

本文通过研究完整子半群来确定可换群的结构，主要结果：Ⅰ若T是可换群G的完整子半群，则T是阿基米德的当且仅当T的极大完整子半群．ⅡG是可换群，T∈Γ（G），则T是特殊的当且仅当，Ⅲ可换群G∈Jω∩Js，若{ST1，ST2…，STr}，是一个Δ的一个浅显序子集，则以下等价：（1）=E0（2）{T1，T2，…，Tn}是Γ（G）的一个极大浅显序子集.（3）Γ（G）的每一条根包含唯一的Ti.（4）G是每一个拯小完整子半群包含唯一的STi.