正则图的最大-团横贯数与减最大-团横贯数 (运筹学与控制论)

本文首先得到了阶数为n、团数为k的连通k-正则图的最大-团横贯数的上界n/k以及n阶连通无爪3-正则图的最大-团横贯数的下界n/4,并对达到这些界的极值图进行了刻画。然后对阶数为n、团数为ω(G)的任意图G的减最大-团横贯数给出了一个紧的下界1+ω(G)-n,同时对阶数为n、团数为k的连通k-正则图的减最大-团横贯数呈现了一个上界n/k,并刻画了达到这个上界的极值图。
     

无三角形3-正则图的几个参数的界

图G的一条边称为割边是指删去该边后,使得余下的图的连通分支数增加。图G中的一个两两不相邻的边子集称为图G的一个匹配。图G的一个最大匹配的边数称为图G的匹配数。图G中的一个与G的每个团都有交的顶点子集称为G的一个团横贯集,图G中元素个数最少的团横贯集的顶点数称为G的团横贯数。本文针对n阶连通无三角形的3一正则图G-（V（G）,E（G））,首先给出了其割边数的一个上界（n—l0）／4;其次对它的匹配数得到了一个下界（11n-2）／24;再次对它的线图的团横贯数呈现了一个上界（13｜E（G）｜＋3）／36。同时刻画了达到这些界的极值图。     

无三角形3-正则图的几个参数的界

图G的一条边称为割边是指删去该边后,使得余下的图的连通分支数增加。图G 中的一个两两不相邻的边子集称为图G 的一个匹配。图G 的一个最大匹配的边数称为图G 的匹配数。图G 中的一个与G 的每个团都有交的顶点子集称为G 的一个团横贯集,图G 中元素个数最少的团横贯集的顶点数称为G 的团横贯数。本文针对n阶连通无三角形的3-正则图G=(V(G),E(G)),首先给出了其割边数的一个上界(n-10)/4;其次对它的匹配数得到了一个下界(11n-2)/24;再次对它的线图的团横贯数呈现了一个上界(13|E(G)|+3)/36。同时刻画了达到这些界的极值图。
     

不含某些图作为导出子图的图的色数

Erods证明了对于任意一个图G,χ(G)-ω(G)可以任意大。因此,对一般图而言,其色数不一定能找到一个与团数有关的上界。文章主要讨论一类特殊的F-free图的色数和团数的关系。设图G=(V,E)是一个不含K1,k+1+e、C4和C4+e为导出子图的连通图,不是星图和奇圈。若α(G)≥k≥3,则χ(G)≤(k(k-1)/2)ω(G)。     

图的边覆盖数、围长和最大亏格

设G为图,用ω(G)和g(G)分别表示图G的边覆盖数和围长.结合图G的边覆盖数和围长等条件,得到了Betti亏数ξ(G)的一个上界,即设G为k-边连通图,则ξ(G)≤{|V(G)|-ω(G)(「)g(G)/2」, k=1,max{1,|V(G)|-ω(G)(k-1)(「)g(G)/2」-1},k=2,3.进而得到最大亏格γM(G)的一个下界.所得结果改进了目前已有的结果.     

不含K1＋P3和C4作为导出子图的图的色数

Erodos证明了对于一个图G ,χ（G）-ω（G）可以任意大。因此,对一般图而言,其色数不一定能找到一个与团数有关的上界。文章主要研究了一类 F-free图的色数和团数的关系。得到了如果图G是一个不含K 1＋ P3和C4作为导出子图的图,那么当α（G ）≥3时,χ（G ）＝ω（G ）;当α（G ）＝2时,χ（G ）n ≤2ω（G ）。     

随机图G（n，P）中k-团的相变性质

随机图G（n,P）模型是随机图理论中最重要的模型之一。该模型中有两个参数n和P,n表示图中的顶点数,P表示图中的任意两个不同顶点之间独立生成边的概率。证明了随机图G（n,P）中存在k一团的临界值为P=n^-2/k-1;同时证明了随机图G（n,P）中具有k≥3顶点孤立团的连通分量数服从均值λ=e^-x-k3/k!的泊松分布;最后,数值实验分析随机图G（n,P）实例中3-团托：和10一团的相变。数值实验结果表明,实验与理论结果相符。     

关于最大的极小k—连通图的构造

本文讨论了如何对已知的 k=k(G)构造一个 n 阶的具有最多边数的极小 k—连通图,同时得出了极小 k—连通图的边数的上界.如果 k 1相似文献   

正盈量二部图的最大匹配数下界的紧性

无向简单图G的亏度（deficiency）是未被最大匹配所覆盖的顶点数；一个二部图G（A，B）具有正盈量（posidve surplus）（对A而言）当且仅当对A的任何非空集合X所包含的顶点数一定小于其邻集所包含的顶点数。对具有正盈量的二部图，刻画了其当亏度def（G）给定时达到最大匹配数下界的二部图，从而验证了此类二部图最大匹配数下界的紧性。     

几类图的全色极大团染色

设G是一个简单图,其顶点集为V(G)而边集为E(G).图G的一个k-染色是指顶点集V(G)到色集{1,2,…,k}的一个映射.如果图G的一个点染色使G的每个极大团所有颜色均出现(这里不要求邻点染色不同),则称该染色为图G的全色极大团染色.而G的全色极大团色数是指能进行全色极大团染色的最大颜色数,记为χmaxcT(G).     

3-临界图独立数的一个结果

1968年,Vizing提出了关于临界图的独立数猜想：若G是n阶的Δ-临界图,则有α（G）≤n/2.利用Vizing邻接引理研究这一猜想,给出了3-临界图的一个上界.     

树的断裂度的紧上界

断裂度是图的哈密尔顿性和容错性的一个有效度量.对连通图G,它被定义为b（G）=max{w（G-S）-S：S是G的点断集},其中w（G-S）表示G-S的分支数.文章研究树的断裂度的上界,得到如下结论：设T是一棵阶为n（≥2）,最大度为Δ的树.若r（n-1/Δ）≠1,则b（T）≤n-2「n-1/Δd」;若r（n-1/Δ）=1,则b（T）≤n-2「n-1/Δ」＋1,其中r（n-1/Δ）和「n-1/Δ」分别表示n-1/Δ的余数和上整数.最后我们用例子说明这个上界是可达的.     

图乘积的分数色数

在文中我们对两个图的强乘积的分数色数进行了研究.任意给定两个图G和H,我们证明了ω(G)ω(H)≤χf(GH)≤χ(G)χ(H),这里ω(G)表示图G的最大团所含顶点的个数,χf(G)和χ(G)分别表示图G的分数色数和色数.从而我们可以通过图G和H本身的性质来对它们的强乘积的分数色数和色数进行估计.     

Kneser图KG(11,5)平方图的色数

Kneser图KG(n,k)的顶点集包括一个n元集的所有k元子集,其中的任意两个顶点相邻当且仅当它们对应的子集不相交.一个图G的平方图G2的顶点集与G的顶点集相同,在G2中两个顶点之间有边当且仅当它们在G中的距离不超过2.通过理论分析和计算机搜索,得到8≤χ(KG2(11,5))≤10,10≤χ(KG2(13,6))≤16,其中前一个结论改进了已知的下界7和上界12.     

图的色数与着色数的上界

证明了对于围长不少于2k1的图G,其色数X(G)≤c((bk,2k+1+2)n)1/k+1+2,其中c=c(k)且limk→∞ c(k)=1,bt,k是G的booksize.另外还证明了对于围长不少于2k+1的图G,其着色数σ(G)≤[bk,2k+1+1)n/2]1/k+2.     

关于图能量上界的注释

对一个简单连通图G V(,E)来说,其能量表示为图G V(,E)的邻接矩阵特征值的绝对值之和.在文献[1]中,Kinkar Ch.Das和Seyed A.Mojallal用定点个数、边数、团数以及顶点的最小度数给出了一个图能量的新上界.在计算验证中我们发现一点瑕疵,本文给予修正,并正确给出修正的图能量的上界.     

完全三部图K_（n_1,n_2,n_3）的竞赛数

对于一个图G,一般情况下计算它的竞赛数k（G）是很困难的。本文给出了关于完全三部图Kn1,n2,n3（n1≥n2≥n3≥2）的边团覆盖数和竞赛数：θe（Kn1,n2,n3）=n1n2 k（Kn1,n2,n3）={n1n2-n1-n2-n3＋4 n1≥n2=n3 n1n2-n1-n2-n3＋3 n1≥n2〉n3