图的强直积的2-距离染色(英文)

设G,H是阶至少为2的简单图。图G与H的强直积是指这样一个图G□×H,其顶点集合为V(G)×V(H),并且(x1,x2)(y1,y2)∈E(G□×H)当且仅当[x1y1∈E(G)且x2y2∈E(H)]或者[x1=y1且x2y2∈E(H)]或者[x2=y2且x1y1∈E(G)]。一个图G的使用了k种颜色的2-距离染色是指一个从V(G)到{1,2,…,k}的映射f,使得任意两个不同的距离最多是2的顶点染不同的颜色。对图G进行2-距离染色所需的最少的颜色数称为图G的2-距离色数,记为χ2(G)。文中将获得两个图的强直积的2-距离色数的可达到的上界和下界:Δ(G□×H)+1≤χ2(G□×H)≤χ2(G).χ2(H)。对一些特殊图,例如Pm□×Kn,Pm□×Wn,Pm□×Sn,Pm□×Fn,Pm□×Cn(n≡0(mod3)或者n=5),给出了它们的2-距离色数。     

扩充竞赛图的控制图

设D=(V,A)是一个有向图,对x,y∈V(D),记O(x)是x控制的顶点的集合,如果O(x)∪O(y)∪{x,y}=V(D),则称x和y控制D。有向图D的控制图记为dom(D),它是一个无向图,顶点集是V(D),且对x,y∈V(D),xy是dom(D)的一条边当且仅当x和y控制D。文章研究扩充竞赛图的控制图,并给出了求解扩充竞赛图的控制图的一个算法。     

直径图为11圈的7距离集研究

如果平面点集X中的任意两点确定的互异距离数为k,则称X为k距离集。用d(x,y)表示平面上互异两点x,y之间的距离,记X中的最大距离为直径D=D(X)。直径图DG(XD)是由X中所有直径构成的图,XD表示其顶点集。讨论了当X是一个7距离集时,直径图DG(XD)的构型。利用DG(XD)中最多包含一个圈,且只能为奇圈的特性,以及直径所具有的特殊性,证得当直径图为11圈时,其顶点集XD恰好为某正十一边形的顶点集。     

距离图的点荫度

实数距离图G(R，D)是顶点集为实数轴上的所有点，顶点u,v∈R相邻当且仅当|u-v|∈D，其中D是一个正实数集．讨论了当D为1到δ的区间时，实数距离图G(R，D)的点荫度．特别地，当3D是某正整数集合，Z是整数集时，得出了整数距离图G(Z，D)的点荫度的几个上界．     

一类环的单位图的控制数

对于一个具有单位元的环R,R的单位图记为G(R).它的顶点是R中的元素,两个不同的顶点x和y相连当且仅当x+y是环R的单位.设G是一个图,V是G的顶点集,D是V的一个子集,若对于V\D的任一点,都存在D中至少一点与之相连,则称D是G的一个控制集,含有顶点数最少的控制集称为图G的一个γ-集,所含的顶点个数称为G的控制数.该文主要研究一类有限环的单位图的控制数,完全确定了当有限交换环R的直和分解恰好是3项时,环R的单位图的控制数.     

交换环的二部本质图

交换环R的本质图EG(R)是一个无向简单图,它以Z(R)\{0}为顶点集,两个不同的顶点x、y之间有一条边相连当且仅当ann(xy)是R的一个本质理想.给出了模n剩余类环Zn的零因子图与本质图相等的充分必要条件.在此基础上,证明了交换环的二部本质图必是完全二部图,并对相应的环进行了同构分类.     

特殊平面图的集合色数

设G是非平凡连通图,记c:V(G)→N是G的一个顶点染色,这里相邻的两个顶点可以着相同的颜色。对于图G的任一顶点v,与v相邻的顶点所着颜色的集称为v的邻色集,记为NC(v)。如果G中任意相邻的两个顶点u,v满足NC(u)≠NC(v),则称c是G的一个集合染色。集合染色所需的最少的颜色数称为G的集合色数,记为χs(G)。本文给出了与轮图有关的一类平面图的集合色数,向日葵图和风车图的集合色数,最后给出了一个猜想。     

两类距离图的分式色数和点色数

分式色数和,点、色数是图的两个重要参数.本文在文献[1]的基础上给出了两类距离图G(Z,Dm,k,k+1)与G(Z,Dm,kk+1,K+2)的分式色数和点色数.     

几类平面图的集合色数

设G是非平凡连通图,记c:V(G)→N是G的一个顶点染色,这里相邻的两个顶点可以着相同的颜色。对于图G的任一顶点ν,与ν相邻的顶点所着颜色的集称为邻色集,记NC(ν)。如果G中任意相邻的两个顶点ν,u满足NC(u)≠NC(ν),则称c是G的一个集合染色。集合染色所需的最少的颜色数称为G的集合色数,记χs(G)。本文给出了团数是3的平面图,没有4圈的平面图及烟花图和风车图的集合色数。     

图Kn-E(Kr),Kr(∪)Kn的整和数

Z表示所有整数的集合.一个有限子集S(∪)Z上的整和图是指图(S,E)中uv∈E当且仅当u+v∈S.图G是整和图,如果它同构于某个子集S(∪)Z上的整和图.图G的整和数是指使(G∪mK1)成为一个整和图时加入的孤立顶点的最少个数m.1994年Harary在[3]中提出了4个未决的问题,本文完整地回答了其中的第一个问题,即确定了图(Kn-E(Kr))的整和数.具体结论如下:ζ(Kn-E(Kr))={0(r=n,n-1)n-1(n-2≥r≥[2n/3]-1)3n-2r-4([2n/3]-1＞r≥n/2)2n-4([2n/3]-1＞n/2≥r≥2)其中n≥5,r≥2,[x]表示不小于x的最小整数.     

一些圈加边图的着色

设P(G;λ)表示图G的色多项式,若P(H;λ)=P(G;λ),称H和G色等价.设ξ是图组成的集合,若对任意图H,当H和ξ中的某一图色等价时,都有H ∈ξ,称ξ是完全色等价类.本文给出了由部分广义多边形树Gsl(a,b;c,d)(s+t=2)组成的一个完全色等价类.     

二部图K(m,n)-A中的色正规图类

设Ｐ（Ｇ,λ）表示简单图Ｇ的色多项式。简单图Ｈ称为与Ｇ是色等价的（记作Ｈ￣Ｇ）,如果Ｐ（Ｈ,λ）＝Ｐ（Ｇ,λ）。简单图类Ｌ称为色正规图类,若对任意Ｈ,Ｇ∈Ｌ使Ｈ￣Ｇ都有Ｈ与Ｇ同构。     

虚二次域Q(a2-4kn)类数的可除性

设D是无平方因子正整数，h(-D)是虚二次域Q(-D)的类数.当D=4kn-a2时，其中a,k,n是适合k＞1，n＞1的正整数，除了几种已知的情况以外，必有n/2｜h(-D)或n｜h(-D).     

使得幂GCD阵（Se）整除幂LCM矩阵［Se］的四元gcd封闭集S的一个刻画

Hong在2002年证明了如下结果:若S为gcd封闭集且|S|≤3,则在|S|阶整数矩阵环M|S|(Z)中,GCD矩阵(S)整除LCM矩阵[S].设e≥1为给定的整数.在本文中,我们给出了关于四元gcd封闭集S的充分必要条件,使得在环M4(Z)中,定义在S上的e次幂GCD矩阵(Se)整除e次幂LCM矩阵[Se].这部分解决了Hong在2002年提出的一个公开问题.     

Finite groups whose element orders do not exceed twenty

Let h(T) denote the number of distinct finite groups G such that 7re( G) = P. Here P is a set of positive integers, and 7r,(G) is the set of element orders of G. It is proved that /i(r)6l0, 1,2, oo| for Tell, 2, 3,"-, 20|.     

完全三部图K（n,n,n＋k）的色性

设Ｇ为简单图,Ｐ（Ｇ,λ）为Ｇ的色多项式。若对任意简单图Ｈ满足Ｐ（Ｈ,λ）＝Ｐ（Ｇ,λ）,都有Ｈ与Ｇ同构,则称Ｇ是色唯一图,设Ｋ（ｍ,ｎ,ｒ）表示完全三部图。证明了（１）对任意非负整数ｋ,若ｎ≥ｋ＋ｋ＾２／３,则Ｋ（ｎ,ｎ,ｎ＋ｋ）是色唯;（２）若ｎ≥４,则Ｋ（ｎ,ｎ,ｎ＋４）是色唯一图。     

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

设Ｐ（Ｇ,λ）表示简单图Ｇ的色多项式;若对任意简单图Ｈ 满足Ｐ（Ｈ,λ） ＝ Ｐ（Ｇ,λ）,都有Ｈ 与Ｇ同构,则称Ｇ是色唯一图;设Ｋ（ｍ ,ｎ,ｒ） 表示完全三部图;本文证明了：（１） 若ｎ ＞ ｋ ＋ ｋ２／３,则图Ｋ（ｎ － ｋ,ｎ,ｎ） 是色唯一的,（２） 若ｎ ≥８,则Ｋ（ｎ － ４,ｎ,ｎ） 是色唯一的;     

一类整数距离图的点荫度

整数距离图以全体整数作为顶点集，顶点u、υ相邻当且仅当｜u-υ｜∈D，其中D是一个正整数集．对于m〉3，令Dm=[1,m]／[1,3]．本研究得到了G（Dm）的点荫度．     

使得幂GCD矩阵$(S^e)$ 整除幂LCM矩阵$[S^e]$的四元gcd封闭集$S$的

洪绍方在 2002 年证明了如下结果： 若 $S$ 为 gcd 封闭集且 $|S| \leq 3$, 则在 $|S|$ 阶整数矩阵环 $M_{|S|}(\mathbf{Z})$ 中,GCD 矩阵 $(S)$ 整除 LCM 矩阵 $[S]$. 设 $e\geq 1$ 为给定的整数. 在本文中,我们给出了关于四元 gcd 封闭集 $S$ 的充分必 要条件,使得在环 $M_4(\mathbf{Z})$ 中, 定义在 $S$ 上的 $e$ 次幂 GCD 矩阵 $(S^e)$ 整除 $e$ 次幂 LCM 矩阵 $[S^e]$. 这部分解决了洪绍方在 2002 年提出的一个公开问题.     

关于完全三部图K(n-k,n,n+k)的色性

设Ｇ为简单图,Ｐ（Ｇ,λ）的色多项式,若对任意简单图Ｈ满足Ｐ（Ｈ,λ）＝Ｐ（Ｇ,λ）,都有Ｈ与Ｇ同构,则称Ｇ是色唯一图,设Ｋ（ｍ,ｎ,ｒ）表示完全三部图,证明了：（１）对任意非负整数ｋ,若ｎ≥２√－３ｋ／３＋ｋ＾２,则Ｋ（ｎ－ｋ,ｎ,ｎ＋ｋ）是色唯一图。（２）若ｎ≥９,则Ｋ（ｎ－３,ｎ,ｎ＋３）是色唯一图。