关于同构图在完全图中置入性的注记(英文)

一个具有m条边的n阶(n,m)图记为G(n,m),本文给了某些G(n,m)在K_n中是i一置入的必要条件,设△(G(n,m))表示G(n,m)中的最大点度.我们证明了下述命题“设G(n,n-l)不含长度为3或4的圈和孤立点,并且不连通.如果△(G(n,n- 1))≤ n-i,此处n>2i,那么 G(n,n-1)在K_n中是i-置入的.”是正确的当且仅当i=l,2,和3.     

非连通图(K_1∨(P_n~(1)∪P_n~(2)))∪P_n~(3)及(K_1∨(P_n~(1)∪P_n~(2)))∪St(n)的优美性

给出了非连通图(K1∨(P(1)n∪P(2)n))∪P(3)n和(K1∨(P(1)n∪P(2)n))∪St(n),且对其优美性进行了研究。证明了如下结论:设n为任意正整数,则当n≥4时,非连通图(K1∨(P(1)n∪P(2)n))∪P(3)n和(K1∨(P(1)n∪P(2)n))∪St(n)均是优美图;其中,Pn是n个顶点的路,Kn是n个顶点的完全图,St(n)是n+1个顶点的星形树,G1∨G2是图G1与G2的联图。     

有关图(P(1)1∨Pn)∪(P(2)1∨P2n)和(P2∨n)∪Gn-1优美性研究

文章给出了非连通图(P1∨Pn)∪St(m)和(P(1)1∨Pn)∪(P(2)1∨P2n)及(P2∨n)∪Gn-1,证明了对任意自然数n,设s=(n)/(2),则当n≥3,m≥s时,非连通图(P1∨Pn)∪St(m)是优美图;当n≥3时,非连通图(P(1)1∨Pn)∪(P(2)1∨P2n)是s-优美图;当n≥2时,非连通图(P2∨n)∪Gn-1是优美图;其中,Pn是n个顶点的路,P1、P(1)1和P(2)1均是只有一个顶点的平凡图,G1∨G2是图G1与G2的联图,St(m)是m 1个顶点的星形树,Kn是n个顶点的完全图,n是Kn的补图,Gn-1是任意一个n-1条边的优美图.     

循环赛图K_(2n)~(i)与完备匹配的新算法

提出了求K2n的△(G)个完备匹配Mi的一种算法。给出了循环赛图的定义。阐明了循环赛图K2n(i)的构造的过程。介绍了循环赛图K(8i),K(1i0),K(1i)4,K(1i)6的构造结果。     

小m条件下的联结数与分数(k,m)-消去图(英文)

设k,m为整数,其中k≥2,m≥0且k≥{2m-1,若k是奇数,2m-2,若k是偶数.本文证明:若图G满足n4k+1-4(k+1-2m)～(1/2),bind(G)((2k-1)(n-1))/(K(n-2)-2m+2),则G是分数(k,m)-消去图.当k是偶数时,若图G满足n4k+1-4(k+2-2m)～(1/2),bind(G)((2k-1)(n-1))/(K(n-2)-2m+3),则G是分数(k,m)-消去图.同时,本文所给结果在一定意思上是最好的.     

无向超环面网的距离参数(英文)

平均距离μ(G),距离控制数γl(G)和距离独立数αd(G)是度量网络性能的重要参数.n维无向超环面网是超立方体的推广.证明了μ(G)=1/d1d2…dn-1n∑i=1(ei2+ei+ei'2-ei'/2·d1d2…dn/di),γ(G)=2当且仅当[e1'+e2'…+en'/2]≤l≤d(G)-1(d1≥d2≥…dn≥4),以及αd(G)=2当[d1+d2+…+dn-2/3]≤d≤d(G)-1(d1≥d2≥…dn≥3).     

对集不交的循环赛图K(i)11与对集的算法

给出了边矩阵和循环赛图的定义.提出了求解完全图K2n+1的△(G)+1个对集Ei的算法,以及对集互交的循环赛图K(1)11,K(2)11,…,K(i)11的构造方法.讨论任意对集Ei及循环图K(i)2n+1的个数问题.介绍了14个对集不交的循环赛图K(1)1,K(2)11,…,K(14)11的构造过程.     

无K_(1,t)图的L(d,1)-T标号

给定一个连通图G=(V,E)及其一棵支撑树T,图G的一个L(d,1)-T标号即函数g:V(G)→{0,1,2,…},满足:(1)如果xy∈E(G),则|g(x)-g(y)|≥1;(2)如果dG(x,y)=2,则|g(x)-g(y)|≥1;(3)如果xy∈E(T),则|g(x)-g(y)|≥d.假设图G有一个L(d,1)-T标号函数g:g(V){0,1,2,…,k},则图G的所有L(d,1)-T标号函数中最小的整数k记为L(d,1)-T标号数λdT(G,T).本文证明了若G是无K1,t(3≤t≤n)的连通图,其最大度为Δ,|G|=n,T为G的任意支撑树,则λdT(G,T)≤tt--12Δ2+Δ+2d-2.     

广义Ramsey数p(n,k)的若干性质

设n ,k≥ 3为自然数 ,p(n ,k)是最小的正整数p ,使得对任何阶图G ,或者G有n点导出子图至少有n - 1条边 ,或者G有k点独立集 ,则本文证明 :( 1 )p(n ,k) ≥max{p(n ,k-1 ) ,p(n- 1 ,k) },( 2 )当n<3k - 4时有p(n ,k) ≥ 2k- 2 + [n/3],这里 [·]是最大取整函数 .     

图有哈密顿(g,f)-因子的度条件

设G是一个n阶2连通图,整数a,b满足2≤a＜b,g(x)和f(x)是定义在V(G)上的两个非负整数值函数,使得x∈V(G),满足a≤g(x)2-(a-1)(b-a)]/(a-1),[n＞(a+b-3)(a+b-2)]/(a-1), 且max｛d_G(x) ,d_G(y) ｝≥(b-1)n/(a+b-2)对G中任意两个不相邻的顶点x,y都成立。     

循环赛图K(i)2n与完备匹配的新算法

提出了求K2n的△(G)个完备匹配Mi的一种算法.给出了循环赛图的定义.阐明了循环赛图K2n(i)的构造的过程.介绍了循环赛图K(i)8,K(i)10,K(i)14,K(i)16+的构造结果.     

循环赛图K(i)2n与完备匹配的新算法

提出了求K2n的△(G)个完备匹配Mi的一种算法.给出了循环赛图的定义.阐明了循环赛图K2n(i)的构造的过程.介绍了循环赛图K(i)8,K(i)10,K(i)14,K(i)16+的构造结果.     

GL(n,Fp)的指数公式

本文给出了有限域F_p上n阶一般线性群的指数公式为x=d(n)·[q-1,q~2-1,…,q~n-1]其中d(n)=min{P~u|P~u≥n},[q-1,q~2-1,…,q~n-1]为整数q-1,q~2-1,…,q~n-1的最小公倍数,这里q=|F_p|=P~r,p=CharF.F_p为特征数为P之有限域,|F_p|=p~r=q,G=GL(n,F_p)为F_p上n阶一般线性群,|GL(n,F_p)|=multiply from i=0 to n-1(q~n-q~i)对任意A∈GL(n,F_p), 使A~m=E之最小正整数m称为G上指数,本文对任意给定的n及F_p,给出了以n,q表示的G的指数公式.     

32阶循环赛图K(1)32与完备匹配的算法

给出了边矩阵及循环赛图的定义,阐明了利用已存在的标明△(G)个完备匹配的2n阶循环赛图K(1)32求解4n阶循环赛图K(1)32的思路,提出了利用边矩阵求解Kv的完备匹配Mi的一种算法,介绍了16阶和32阶循环赛图K(1)16,K(1)32的求解全过程.     

关于D_(2n)型Chevalley扩群的存在唯一性(英文)

构造出了任意域K上D_(2n)型泛Chevalley群G≌Ω_(4n)(K,f_D)的扩群G和相应的映射,使图(1)交换且行列都正合,并证明了G在同构意义下是唯一的。     

关于Erds-Ginzburg-Ziv定理的一个注记(英文)

设G为n阶加法Abe1群 ,S ={ai} 2n- 1 i=1 是G中元序列 ,对a∈G用r(S ,a)表示a写成S中n项之和的方法数 .196 1年Erd s ,Ginzburg与Ziv证明了n为素数时r(S ,0 )≥ 1.1996年高维东指出n是素数 p时 r(S ,0 )≡ 1(mod p) .证明了下述结果 :假定有特征为素数 p的域使G为其加法子群 ,则r(S ,0 )≡ 1(modp) ,且对a∈G \{ 0 }有r(S ,a)≡ 0 (mod p) .这推广了高维东的工作 .     

半群T_(n,r)的极大(正则)子半群的完全分类

设S_n和T_n分别是X_n={1, 2,…,n}上的对称群和全变换半群.对1≤r≤n,令T(n,r)={α∈T_n:|im(α)|≤r},则T(n,r)是全变换半群T_n的双边理想.对1≤r≤n-1,考虑半群T_(n,r)=T(n,r)∪S_n,得到了半群T_(n,r)的极大子半群S有且仅有两类:S=T_(n,r)\[τ_i](1≤i≤p=p_r(n))和S=T(n,r)∪G,其中G是群S_n的极大子半群.同时,证明了半群T_(n,r)的极大子半群和极大正则子半群是一致的.所得结果推广了已有的结果.     

三部图K(m,n,r)-A(|A|=2)的色唯一性

设G是简单图,用P(G,λ)表示图G的色多项式,令K(m,n,r)表示完全三部图.证明了1)当3≤m≤n≤r时,令s=1/√6√(n-m)2 (r-n)2 (r-m)2 12,若m n r＞2√3s 3s2,则K(m,n,r)-A(|A|=2)是色唯一图;2)当m≥4时,K(m,m,m)-A,K(m,m,m 1)-A,K(m,m 1,m 1)-A,(|A|=2)都是色唯一图;3)设n,k为非负整数,则当n＞k2 2√k2 6 k 2时,K(n-k,n,n)-A;当n＞k2 2√k2 6-k/3 2时,K(n,n,n k)-A;当n＞2√3k2 6 k2 2时,K(n-k,n,n k)-A(|A|=2)均为色唯一图.     

完全三部图K(n-k,n-v,n)的色唯一性

设P(G,λ)是图G的色多项式,如果任意与图G的色多项式相等(P(G,λ)=P(H,λ))的图H都与图G同构(GH),则称图G是色唯一图.文献[Lau G C,Peng Y H.Chromatic uniqueness ofcertain complete tripartite graphs.Acta Mathematica Sinica,English Series,2011,27(5):919-926]中提出一个猜想(若k≥v≥2,n≥k2/4+v+1,则完全三部图K(n-k,n-v,n)是色唯一的),并证明了若2≤v≤4,k≥v≥2,n≥k2/4+v+1,则K(n-k,n-v,n)是色唯一的.通过比较三角形子图和无弦四边形子图的个数,证明了若v≥4,k≥2v2+4,n≥(k+2)2/8+3,则K(n-k,n-v,n)是色唯一图。     

循环图C_(2n)(1,3)的2-偶匹配可扩性

设图G是一简单的且有完美匹配的连通图,称图G是k-偶匹配可扩的,是指G的每一个基数不大于k(1≤k≤(│V(G)│-2)/2)的偶匹配M都可以扩充为G的一个完美匹配.刻画了循环图C2(n1,3)的2-偶匹配可扩性,得到结论:对于任意的n(n≥3),C2(n1,3)是2-偶匹配可扩性的.