无三角形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是n阶3－边连通图，若对任意G的边数为3的最小边割E都满足G－E遥每一连通分支的阶至少为（n-1）／10，则或者G是超欧拉图，或者G可收缩为G‘＝Petersen图，且G‘的每个顶点在G中的原像是G的一个可折叠子图，其顶点数至少是（n-1）／10。     

3元立方体的匹配排除

设E是图G的一个边子集,若G-E中既没有完美匹配也没有几乎完美匹配,则称E为G的一个匹配排除集.边数最少的匹配排除集的基数,称为图G的匹配排除数.文章给出了3元立方体的最优匹配排除数.     

路径幂图、Flower Snark图及多锥图独立数

图的独立数是图论中的重要参数,令G=(V(G),E(G))是一个简单有限无向图.如果V(G)的子集S中任意两个顶点均不相邻,则S是图G的一个独立集.顶点独立集大小的最大值,称为图G的独立数,记做α(G).研究了路径幂图、Flower Snark及其相关图、多锥图的独立数问题,首先构造出了它们的独立集,得到其独立数的下界,然后证明了该值也是其独立数的上界,并给出了它们独立数的准确值.     

单圈图的k-距离匹配控制数

单圈图是边数等于顶点数的连通图.令G=(V,E)是无孤立顶点的图,若集合DV(G)是G的一个k-距离控制集且导出子图〈D〉有完美匹配,则称D是G的一个k-距离匹配控制集.k-距离匹配控制数γkp(G)是G的最小k-距离匹配控制集的势.主要证明了单圈图k-距离匹配控制数的一个重要引理,由此找到了单圈图k-距离匹配控制数的上界,并构造了极图.     

k元n方体的最优条件匹配排除集

设E是图G的一个边子集,若G-E中既不包含孤立点,也没有完美匹配和几乎完美匹配,则称E为G的一个条件匹配排除集.边数最少的条件匹配排除集,称为最优条件匹配排除集.文章给出了k元n方体的最优条件匹配排除集.     

折叠交叉立方体的限制连通度

限制性连通度作为评估互联网络容错性的最佳参数之一,在多处理器系统中对可靠性计算起着重要作用.给定一个连通图G=(V,E)和一个非负整数h,子集F?V(G)(F?E(G))(如果存在)称为h-限制点割(h-限制边割),如果G-F不连通,并且G-F中的每个连通分支至少有h+1个顶点,其中最小的h-限制点割(h-限制边割)的基数称为图G的h-限制连通度(h-限制边连通度),记为κh(G)(λh(G)).本文确定了h=2时n-维折叠交叉立方体FCQn的κh(G)和λh(G).     

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

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

几类图的全色极大团染色

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

图中顶点子集的边连通度与最优分级边连通图的构造问题

G =(V ,E)是无向连通图 ,无环允许有重边 .S是V的至少包含两个顶点的子集 ,S的边连通度λG(S)被定义为使S中的顶点不属于同一连通分支所需去掉的最少边数 .给定集合V和V的一个划分V =V1∪V2 ∪…∪Vr(|r|≥ 1,|V1|≥ 2 )以及正整数序列k1>k2 >… >kr≥ 2 .记Si=V1∪V2 ∪…∪Vi,1≤i≤r.构造一个连通图G =(V ,E)满足 :λG(Si)≥ki(1≤i≤r)且边数 |E|最小 .这种图G称为与所给划分和正整数序列相对应的最优分级边连通图 .在给出顶点子集的边连通度概念的基础上 ,本文提出并讨论了有关最优分级边连通图的构造问题