完全二部图上的筹码分发博弈

本文主要研究完全二部图上的筹码分发博弈(chip-firing games)次数的有限性。我们根据顶点的筹码数,定义两个函数并进行分类;结合完全二部图的性质,给出了博弈次数有限的充要条件。

完全二部图K_(4,n)的点被多重集可区别的E-全染色

利用反证法、色集合事先分配法及构造具体染色等方法,讨论完全二部图K_(4,n)的点被多重集可区别的E-全染色,并确定K_(4,n)的点被多重集可区别的E-全色数.

完全二部图K5,n(n ≥ 7114)的点被多重集可区别的E-全染色

利用反证法、色集合事先分配法以及构造具体染色等方法,探讨了完全二部图K5,n(n ≥ 7114)的点被多重集可区别的E-全染色,确定了这一类图的点被多重集可区别的E-全色数。

一类定向完全二部图的秩

图谱理论是代数图论和组合矩阵论中重要的研究领域,图所对应的各类矩阵是图谱理论的重要研究方向和研究内容.本文主要根据邻接矩阵,将图D的秩r(D)定义为邻接矩阵的秩,基于完全二部图K 2,n的定向图,即每条边x i~y j都被赋予一个定向:x i→y j或x i←y j,通过导出子图及孪生点的相关定理,刻画了这类定向完全二部图的秩.

完全二部图的路和星分解

主要研究完全二部图的{路,星}-分解.设p,q为非负整数,得到了完全二部图K_(2k,n)可以分解为p条路P_(k+2)(P_(k+3))和q个星S_(k+1)的充要条件,以及完全二部图K_(k,n)可以分解为p条路P_(k-1)和q个星S_(k+1)的充要条件.

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

设G是一个简单图,f为G的一个E-全染色.对任意点x∈V(G),用C(x)表示在f下点x的色以及与x关联边颜色所构成的集合.若u,v∈V(G),u≠v,有C(u)≠C(v),则f称为图G的点可区别E-全染色,简称VDET染色.图G的VDET染色所用颜色数目的最小值称为图G的点可区别E-全色数(简称为VDET色数),记为χevt(G).利用分析法和反证法,讨论并给出完全二部图K3,n(3≤n≤17)的点可区别E-全色数.

完全二部图K_(2,n)和K_(3,n)的一般点可区别全染色

借助已有的完全二部图K_(2,n)和K_(3,n)的点可区别IE-全色数的结论,利用组合分析及构造具体染色的方法探讨完全二部图K_(2,n)和K_(3,n)的一般点可区别全染色问题,确定了K_(2,n)和K_(3,n)的一般点可区别全色数.

完全二部图K_(4,n)的点强可区别全染色

设G=(V,E)是简单图,f是从V∪E到{1,2,…,k}的一个映射,其中k是正整数.对任意x∈V,令C(x)={f(x)}∪{f(y)|y∈V,y和x相邻}∪{f(e)|e∈E,e和x相关联},称之为x在f下的色集合.若:(i)对任意uv∈E,f(u)≠f(v),有f(u)≠f(uv),f(v)≠f(uv);(ii)对任意uv,uw∈E,v≠w,有f(uv)≠f(uw);(iii)对任意u,v∈V,u≠v,有C(u)≠C(v),则称f是图G的一个使用了k种颜色的点强可区别全染色,简记为k-VSDTC.称χvst(G)=min{k|G存在k-VSDTC}为G的点强可区别全色数.得到了完全二部图K4,n(n>4)的点强可区别全色数.关键词:完全二部图;正常全染色;点强可区别全染色;

完全二部图的拓扑指数

图的拓扑指数是应用图论中研究的主要课题之一,在信息科学、物理和化学中有着重要的应用。基于顶点度、特征值、距离的完全二部图的几类拓扑指数被研究,并给出了准确值。

轮、扇以及完全二部图K_(1,n)和K_(2,n)的点可区别VE-全染色(英文)

设G是阶至少为2的简单图.在点可区别正常全染色的基础上,提出了图G的点可区别一般全染色,即VE-全染色,并且得到了轮、扇和完全二部图K1,n和K2,n的点可区别VE-全色数,据此提出了一个猜想.

两个完全二部图的匹配和的L(2,1)-标号

研究了两个均同构于完全二部图Km,n的图G1=(X1,Y1)与G2=(X2,Y2)的匹配和Bm,n的L(2,1)-标号问题,得到了下面的结果:(1)若X1中元素完全与X2中元素相匹配且m,n>3,则Bm,n的L(2,1)-标号数为m+n;(2)若X1中元素不完全与X2中元素相匹配且m,n>6,则Bm,n的L(2,1)-标号数为m+n+1.

完全二部图的Mycielski图的点可区别全色数

图的一个正常的全染色如果满足不同点的点及其关联边的色集合不同,则称该染色法为点可区别全染色,其所用最少颜色数称为该图的点可区别全色数.给出了完全二部图的Mycielski图的点可区别全色数.

完全二部图K_(3,3)与星S_n的积图的交叉数

确定图的交叉数是NP-完全问题.目前有关完全二部图与星图的积图的交叉数结果并不多.引入了一些新的收缩技巧,建立了积图K_(3,3)□S_n与完全三部图K_(3,3,n)之间的交叉数关系.从而,为进一步完全确定积图K_(3,3)□S_n的交叉数提供了一条新途径.

完全二部图K_(9,n)的点可区别IE-全染色(英文)

G是一个简单图,G的一个IE全染色f是一个映射,该映射满足:对u,v∈V(G),u≠v,有C(u)≠C(v).图G的一个点可区别IE-全染色f是指一个从V(G)∪E(G)到{1,2,…,k}的映射,且满足:对uv∈E(G),有f(u)≠f(v);对u,v∈V(G),u≠v,有C(u)≠C(v),其中C(u)={f(u)}∪{f(uv):uv∈E(G)},简称k-VDIET.数min{k:G有一个k-VDIET染色}称为图G的点可区别IE-全色数或简称VDIET色数,记为χievt(G).本文讨论并给出了完全二部图K9,n的点可区别IE-全色数.

完全二部图K_(4,n)(n≥47)的点可区别E-全染色

G是一个简单图,G的一个E-全染色f是指使相邻顶点着不同颜色且每条关联边与它的顶点着以不同颜色的全染色。设f为G的一个E-全染色,对任意x∈V(G),用C(x)表示在f下顶点的颜色以及与x关联的边的颜色所构成的集合。若任意u,v∈V(G),u≠v,有C(u)≠C(v),则称f是图G的点可区别的E-全染色,简称VDET染色。图G的VDET染色所用颜色数目的最小值称为图G的的点可区别E-全色数或简称VDET色数,记为χ_vt^e(G)。讨论并给出了完全二部图K_(4,n)(n≥47)的点可区别E-全色数。

完全图与完全二部图上的Hopf代数结构

分别在完全图,完全二部图及完全r部图的向量空间上建立了Hopf代数结构,并指出它们分别与一元多项式Hopf代数,二元多项式Hopf代数及r元多项式Hopf代数是同构的.

二部图半群和完全二部图半群

讨论了二部图半群和完全二部图半群的一些性质,探讨了二部图半群与二部图、完全二部图半群与完全二部图的关系,给出了二部图半群的圈特征。

完全二部图全着色的构造

利用全着色矩阵给出完全二部图全着色的构造,该构造可以方便快捷对完全二部图进行全着色.

完全二部图的P_5—因子分解

本文给出了完全二部图的P5—因子分解存在的必要条件，同时讨论了充分条件的几种情况，给出了四个猜想。

关于完全二部图的P_(2k+1)—因子分解

本文给出了完全二部图Km ,n的P2k +1—因子分解存在的必要条件 ,同时论证了充分条件的二种特殊情况。