几种图的棱凝聚度的最小值上界的讨论

本文利用明格尔定理,惠特尼定理及文献[1]的结论,对λ(G)=δ(G)=n 的一类图证明了它的棱凝聚度的最小值上界为[n/2].并同时证明了极小 n——连通图棱凝聚度的最小值上界为1.     

对一类图的棱凝聚度最小值上界的估计

本文对δ(G)≥[p+1/2]的一类简单连通图棱凝聚度的最小值上界给出进一步的估计,並指出这个最小值如果不是负整数,只能是0,或者是1。     

关于广义棱连通度的一个注记

将广义棱α（G）的定义推广到m＋1个同构图的情形,定义了图a^m（G）,得到广义棱矿（G）的点连通度和边连通度的几个性质．     

每点都与3度点相邻的最大临界3棱连通图的结构

没G=(V,E)是3棱连通图,若对每个x∈V(G),G-x 不是3棱连通的,则称G 为临界3棱连通图.p 阶临界3棱连通图的全体记为(?)_3(p),G∈(?)_3(p)称为最大的,如果不存在H∈(?)_3(p),使|E(H)|>|E(G)|.本文给出每个点都与3度点相邻的p 阶最大临界3棱连通图的结构.     

极小n棱连通图的着色与棱数

Mader证明极小n连通图是n+1色可着的,本文证明极小n棱连通图也是n+1色可着的。并且对极小n棱连通图的棱数界进行了估计,证明了若G是p阶极小n棱连通图,则G的棱数e(G)≤n(p-1)。     

具有棱凝聚度≤1的顶点之个数估计

本文证明:当简单图G的棱连通度λ=1或当G的阶n≤2λ(λ≥2)时,G的任何点x部满足其梭凝聚度c’(x)≤1; 而当n>2λ(λ≥2)时,满足c’(x)≤l的顶点x的数目至少有(λ+2)个。     

简单连通图的反比度和几何反比度

反比度和几何反比度是Ｇｒａｆｆｉｔｉ猜想程序中首先出现的关于图的两个量。本文研究了它们的性质，从面确定其上下界。     

关于指数为（h＋1）的临界h棱连通图的最大棱数

令N 是正整数集合.设p,h∈N,令(?)_h~1(p)是其指数不为1的p 阶临界h 棱连通图集合,f_h~(?)(p)是一个确定的二元函数.本文证明如下结论:设h,p_0∈N,p≥4h-2,h≥4且设G 是(?)_h~1(p_0)中具有最大棱数且指数为h+1的图.如果对任何p∈N 且p相似文献   

一类图的邻强边色数的上界

证明了当图G的最大度Δ(G)恰以n的某个函数为界时,G的邻强边色数χ′as(G)≤│cn│,其中0相似文献   

强边着色猜想问题的最优图

著名图论专家Erds和Nesetǐil对图的强边色数上界提出了一个猜想:当最大度Δ为偶数时,χ's(G)≤5/4Δ~2;当最大度Δ为奇数时,χ's(G)≤1/4(5Δ~2-2Δ+1);并且给出了当Δ=4时的最优图.此处构造了一族图,并证明了当最大度为奇数时,如果Erd9s和Ne2etǐil提出的强边着色猜想成立,则猜想中的上界是最优的.     

图的最小覆盖的逻辑算法

给出了利用命题逻辑公式的析取范式和主析取范式求图的全部极小覆盖和最小覆盖以及全部极小边覆盖和最小边覆盖的一般算法．     

p部图的Kirchhoff指标上界

对n阶P部图G=G(NI,N2,…,Np)(|Ni|=ni,i=1,2,…,p;n1≤n2≤…≤np),得到其Kirchhoff 指标的可达上界,且表明:若2np-n≤1,当其同构于路pn时达到上界;若2np-n≥2,当其同构于树T1(n1,n2,…,np-1;np)时达到上界.     

一类图的可加边问题

文章主要讨论了在A类割集是割点和A类割集不是割点且不是团两种情况下处处h-可断图的可加边问题，并得出处处h-可断图在这两种情况下存在可加边。依据A类割集及处处h-可断图的性质，文章给出了由处处h-可断图出发构造新的处处h可断图的一种方法。     

蛛网图的邻强边染色

蛛网图是一个重要的网络拓扑结构,研究它的染色对于网络权的分配和通信网络的设计有重要的指导作用.利用穷举法和组合分析法讨论了蛛网图的邻强边染色,得到了蛛网图的邻强边色数.     

点可区别边色数的一个上界

设G是简单图,f是从V(G)∪E(G)到{1,2,…,k]的一个映射.对每个u∈V(G),令C(u)={f(uv)|v∈V(G),uv∈E(G)].如果f是k-正常边染色,且对任意u,v∈V(G),有C(u)≠C(v),那么称f为图G的点可区别边染色(简称为k-VDEC).数x's(G)=min{k|G有k-VDEC}称为图G的点可区别边色数.本文通过应用概率方法,证明了对任意最大度△≥2的图G,x's(G)≤16△.     

λ'-最优无三角图的最小边度充分条件

设S是连通图G的一个边割。若G-S不包含孤立点,则称S是G的一个限制边割。图G的最小限制边割的边数称为G的限制边连通度,记为λ'(G).如果图G的限制边连通度等于其最小度,则称图G是最优限制边连通的,简称λ'-最优的。设G是一个n阶的连通无三角图,且最小度δ(G)≥2.文章证明了,若最小边度ξ(G)≥(n/2-2 )(1+1/δ(G)-1),则G是λ'-最优的。并由此推出,若连通无三角图G的最小度δ(G)≥n/4+1,则G是λ'-最优的。最后给出例子说明这些结果给出的边界都是紧的。     

关于点赋权图的赋权控制数的一个上界

点赋权图Gw=（V,E,W）是指对简单图G的顶点集作一个赋权函数W：V→R^＋。在图G所有的控制集D V（G）（V（G）／D中的任意顶点v都与D中的点关联）中最小的权和W（D）称为图Gw的赋权控制数。记作γw（Gw）。证明了对基数为N,平均权为W^-的图Gw,其赋权控制数γw（Gw）≤Nw^-1δ＋1^——1＋1n（δ＋1）。