Cartesian积与邻点可区别着色之间的关系（英文）

图G的一个正常k-边着色是指k种颜色1,2,…,k对图G各边的一个分配,使得任意2条相邻边染以不同的颜色.对于图G的一个正常边染色f和G中任何一个顶点x,Sf(x)或S(x)表示与顶点x关联的边在f下的颜色所构成的集合.若对于图G中任意2个相邻顶点u和v,有S(u)≠S(v),则称f为图G的邻点可区别正常边染色.对图G进行邻点可区别正常边染色所需的最少颜色数,称为G的邻点可区别正常边色数,记为χ′a(G).图G的一个正常k-全染色是指k种颜色对图G的顶点和边的一个分配,使得任意2个相邻的或相关联元素染以不同的颜色.对于图G的一个正常全染色g和G中任何一个顶点x,使用Cg(x)或C(x)来表示顶点x的颜色(在g下)以及与顶点x关联的边在g下的颜色所构成的集合.若对于G中任意2个相邻顶点u和v,有C(u)≠C(v),则称g为图G的邻点可区别全染色.图G的邻点可区别全染色所需的最少颜色数称为图G的邻点可区别正常全色数,记为χ″a(G).主要讨论了Cartesian积和2种邻点可区别染色之间的关系.     

K1,5,p和K1,6,p的点可区别的IE-全染色及一般全染色

利用色集事先分配法、构造染色法和反证法,探讨了完全三部图K_1,5,p和K_1,6,p的点可区别IE-全染色和点可区别一般全染色问题,确定了K_1,5,p和K_1,6,p的点可区别IE-全色数和点可区别一般全色数.     

Cartesian积与邻点可区别着色之间的关系

图G的一个正常k-边着色是指k种颜色1,2,…,k对图G各边的一个分配,使得任意2条相邻边染以不同的颜色.对于图G的一个正常边染色f和G中任何一个顶点x,S_f（x）或S（x）表示与顶点x关联的边在f下的颜色所构成的集合.若对于图G中任意2个相邻顶点u和v,有S（u）≠S（v）,则称f为图G的邻点可区别正常边染色.对图G进行邻点可区别正常边染色所需的最少颜色数,称为G的邻点可区别正常边色数,记为χ'_a（G）.图G的一个正常k-全染色是指k种颜色对图G的顶点和边的一个分配,使得任意2个相邻的或相关联元素染以不同的颜色.对于图G的一个正常全染色g和G中任何一个顶点 x,使用C_g（x）或C（x）来表示顶点x的颜色（在g下）以及与顶点x关联的边在g下的颜色所构成的集合.若对于G中任意2个相邻顶点u和v,有C（u）≠C（v）,则称g为图G的邻点可区别全染色.图G的邻点可区别全染色所需的最少颜色数称为图G的邻点可区别正常全色数,记为χ″_a（G）.主要讨论了Cartesian积和2种邻点可区别染色之间的关系.     

完全二部图K_(10,n)(215≤n≤466)的点可区别E-全染色

图G的一个E-全染色是指使相邻点染以不同的颜色,且每条关联边和它的端点染以不同的颜色的全染色。对图G的一个E-全染色f,一旦对图G中任意互不相同的两点u, v,有C(u)≠C(v),其中C(x)表示在f下点x的颜色以及与x关联的边的色所构成的集合,那么f称为图G的点可区别的E-全染色,简称为VDET染色。令χ_(vt)~e(G)=min{k|G存在k-VDET染色},称χ_(vt)~e(G)为图G的点可区别E-全色数。运用分析法和反证法,讨论并证明了完全二部图K_(10,n)(215≤n≤466)的点可区别E-全色数。     

六角系统的全色数

本文研究了六角系统图Ｇ的全色数，得到Ｘｒ（Ｇ）＝△（Ｇ）＋１。其中△（Ｇ）、Ｘｒ（Ｇ）分别表示Ｇ的最大度和全色数。     

完全三部图的点可约全染色

设f:V(G)∪E (G)→{1,?,k}是图G的一个(非正常)k-全染色,其中1≤k≤Δ+1。若对任意两个顶点u,v∈V (G)且d (u)=d (v)时,满足S (u)=S (v),则称f是图G的一个点可约k-全染色,其中S(u)表示顶点u和点u的关联边上分配的颜色组成的色集合。运用图的色集合事先分配法、组合分析法和构造染色法,结合完美匹配探讨了完全三部图K_m,n,p的点可约全染色问题,进一步确定了K_m,n,p的点可约全色数。     

随机图的邻点和可约边标号算法

如果对于一个点数为p,边数为q的图G(p,q),存在映射f:E(G)→{1,2,…,q},并且对于任意两个同度相邻点u,v存在Sum(u)=Sum(v),其中■,称f为图的邻点和可约边标号。在已有的点魔幻边标号和点可约边染色研究的基础上,结合实际应用,提出了邻点和可约边标号的新概念,并设计了邻点和可约边标号(adjacent vertex sum reducible edge labeling,AVSREL)算法。算法通过循环迭代寻优的方式,对图进行标号,得到了10个点内所有非同构图的标号结果,经过结果分析总结出若干定理并加以证明。     

六角系统的边面点面全色数

本文得到了六角系统的边面和点面金色数．     

扭smash积的整体维数

建立了H-双模代数A和它的扭smash积A＊H的整体维数之间的关系.     

三值扭环形计数器的研究

本文根据二值扭环形计数器的设计思想,提出了三值扭环形计数器基于模代数的三 值D 型 和 J K 型 触发器仁`〕的电路设计.在此基础上,进一步提出了借助于三值 K 图化简技术,设计具有自校正功能的三值扭环形计数器的方法     

列表双临界图（英文）

G是k-可着色的连通图,如果对于G中的所有边uv,都有G-u-v是(k-2)-可着色的,则称图G是双临界图.由Erdo?s和Lova′sz提出了一个长期未能解决的猜想:完全图是唯一的双临界图[1].连通图G称为边双临界图,如果G中包含多对不相邻的边,并且对于任意一对不相邻的边e1,e2,都有χ(G-e1-e2)=χ(G)-2,其中χ(G)表示图G的色数.Kawarabayashi等人[2]及后来的Lattanzio[3]证明了完全图是唯一的边双临界图.文章证明了在图G中,对于任意的两个点u,v∈V(G),如果ch(G-u-v)=ch(G)-2,则图G是完全图,其中ch(G)表示G的选择数,还证明了完全图是唯一的列表双临界图.     

路图P3(G)的色数

设G是一个图,G的路图P3(G)的顶点集是G中所有三个顶点的路P3, 当G中的两个P3路形成P4路或C3圈时,在P3(G)中它们所代表的两个顶点相邻. 在这篇文章中,我们得到对于一个无三角形的图G, χ(P3(G))≤β(G),其中β(G)表G的点覆盖数. 对于顶点数至少为3的连通图G,χ(P3(G))≤2当且仅当G是二部图, 并且χ(P3(G))=1当且仅当 G是星图. 对于K4的剖分图G,2≤χ(P3(G))≤3. 对于系列平行图和外可平面图G,χ(P3(G))≤3.     

社会网络中影响集选择的一个近似算法

在研究社会网络影响集的选择问题中,目标是选取网络G中的一个最小点集S,使得V（G）-S中的每个点都至少有一半邻点在S中.本文给出一个α（△＋1）/δ＋1-近似算法,其中δ和△分别表示图G的最小度和最大度,α是局部独立数,它指示着图G的局部区域中最多含有的独立点的个数.     

图P_m∨P_n,P_m∨C_n与P_m∨F_n的第一类弱全色数

给出路与路、路与圈、路与扇的第一类弱全色数:(1)对Pm∨Pn,则有χfwt(Pm∨Pn)=max{m,n}+2,(2)对P2∨C3,则有χfwt(P2∨C3)=5,(3)对Pm∨Cn,则有χfwt(Pm∨Cn)={max{m,n}+2,n≡0(mod 2)max{m,n}+3,n≡1(mod 2),其中m≥3,n≥3,(4)对Pm∨Fn,则有χfwt(Pm∨Fn)=m+n+1。     

关于Jacobsthal数和Jacobsthal-Lucas数的r-循环矩阵的行列式和逆

和 是n阶r-循环矩阵, 其中 , 是Jacobsthal数, , 是Jacobsthal-Lucas数, 研究得出了 和 的关于Jacobsthal数和Jacobsthal-Lucas数的行列式的值. 同时, 计算出了矩阵 和 的逆.     

图的非自中心数（英文）

许克祥等人在文献[1]中定义了新的基于离心率的图不变量,称之为图的非自中心数(简称NSC数),记为N(G).图的非自中心数定义为N(G)=∑_({v_i,v_j}V(G)|e_i-e_j|,这里ei表示顶点vi的离心率,在文献[1]中,同其他结果一起,作者确定了一些图的N(G)数的上界和下界并且刻画了达到上下界的极图.但是作者给出的极图的刻画是不完全的.基于他们得到的研究结果,在本文中我们给出了达到上下界的所有极图的完全刻画.另外,我们还给出了阶为n直径为d的树T的N(T)数的下界并且确定双圈图和含有奇数个顶点的三圈图的NSC数的上界.     

增广立方体的2-额外连通度

增广立方体AQ_n是超立方体Q_n的一个变体,它不仅保留了超立方体Q_n的几乎所有特征,还具有Q_n不具有的一些嵌入特性.本文利用图结构分析的方法讨论了增广立方体AQ_n的2-额外点(或边)连通度,证明了κ₂(AQ_n)=6n-18(n≥6),λ₂(AQ_n)=6n-7(n≥5)。该结论对衡量互联网络的可靠性和容错性有借鉴意义。     

有向图及乘积图的路由数

s-图的路由数源自于网格上行走的机器人的坐标规则问题．Onn和Sperner指出该问题是NP-完全的并进而提出这样一个问题：平面图上的路由数是否一定存在仅由半径为参数构成的界？本文引入有向s-图的路由数这一概念并证明该数等于其周长．这一结果表明无向s-图的路由数等于该图所有定向图的最小周长，同时也对上面的问题给出了一个反例．做为一个应用．我们证明乘积图的路由数等于其半径．     

关于临界h棱连通图的最大棱数及最大图的结构(Ⅱ)——临界h棱连通图的性质和最大临界3棱连通图类的刻划

设λ(G)表示G的棱连通度,图G称为临界h棱连通的,如果λ(G)=h而且对任何x∈V(G),λ(G-x)≤h-1,具有最大棱数的临界h棱连通图称为最大临界h棱连通图.本文首先证明对h≥3的临界h棱连通图的若干性质,然后证明最大临界3棱连通图的每个顶点都与3度点相邻,并由此给出了此类图的结构刻划和最大棱数.     

基于谱系数图检测特殊逻辑函数的图形方法

阐述了特殊函数——冗余函数、线性函数、自反函数、自双反函数的定义.讨论了它们的有关谱系数的性质.据此提出了这四个函数的特点的四个定理, 给出了相应谱系数图的特点,得到了基于谱技术的谱系数图检测冗余函数、线性函数、自反函数、自双反函数的新方法.实例展示了基于上述定理的谱系数图检测上述函数的过程. 实例表明该方法具有直观、简单等特点.