图的伪对集

本文定义了图的伪对集是可以含有环的对集,给出了一个图有完美伪对集的充分必要条件并证明了有关最大伪对集的两个定理,从而推广了Tutte及Berge的对集定理。     

k-连通无爪图中存在哈密尔顿圈的一个隐度条件

文中给出了强基本独立集的概念,并证明了如下定理:设G是一个具有n个顶点的k-连通无爪图,其中k≥2.如果对任意一个具有k个顶点的强基本独立集S,都有max{d2(x)|x∈S}≥n 2,则G是哈密尔顿图.此定理在无爪图的条件下推广了已有的几个有关图中哈密尔顿圈存在性的定理.     

k-连通图中存在哈密尔顿圈的一个隐度条件

文中给出了强基本独立集的概念,并证明了如下定理:设G是一个具有n个顶点的k-连通图,其中k≥2.如果对任意一个具有k个顶点的强基本独立集S,都有max{d1(x)|x∈S}≥n/2,则G是哈密尔顿图.此定理推广了已有的几个有关图中哈密尔顿圈存在性的定理.     

基于改进的粘贴模型求解图最大独立集的DNA算法

改进的DNA粘贴模型在解决SAT问题时所需的寡核苷酸片段数量有显著降低,对改进的粘贴模型做了进一步的改进,建立了图最大独立集的一种改进的DNA粘贴模型.首先将图的独立集问题转化为可满足性问题,然后利用本文改进的粘贴模型给出了图的最大独立集的DNA算法.最后通过一个实例给出算法实现并求出了最大独立集.     

关于几乎正则2-连通图的Hamilton性的注记

研究几乎正则图的Hamilton性,得到了定理1　设G是2连通的(k,k 1)图,并且k≥V(G)3 13,如果G是偶数阶的图,则G是Hamilton图.定理2　设G是(k,k 2)图,并且k≥n3 103,如果存在G的一个非空独立集B1,使得B1≥n3-133,而且对于G的所有独立集B,都有B≤n2-1,则G是Hamilton图.     

关于图的Hamilton性的一个新结果

利用插点方法就k 连通图G的本质独立集的邻域交研究图的Hamilton性 ,得到了关于图的Hamilton的一个新的充分条件 .这个结果改进和推广了Ore定理     

基于DNA自组装模型解决图的最大独立集问题

为了寻找图的最大独立集问题,先利用DNA自组装模型解决可满足性问题,再把最大独立集问题转化为可满足性问题,从而解决最大独立集问题。整个过程只用到凝胶电泳操作,在很大程度上减少了误差。     

关于Erds的一个问题

讨论了Erds提出的关于图的最大完全图与最大独立集的一个问题。     

给定独立数的无符号拉普拉斯谱半径的下界

设图G为简单连通图,图G的独立数α=α(G)指的是图中顶点独立集最大基数,本文确定了给定独立数α=n-2,n-3条件下一类n阶连通图的无符号拉普拉斯谱半径的下界。     

关于Hosoya指标和Merrifield-Simmons指标的k色极图

图的Hosoya指标定义为图中包含空边集在内的对集总数.图的Merrifield-Simmons指标定义为图中包含空点集在内的点独立集总数.考虑点数为n的k色连通图的集合Gn,k,证明了Tur n图Tn(k)是Gn,k中Hosoya指标最大且Merrifield-Simmons指标最小的图,还确定了k=2,3时Gn,k中Hosoya指标最小且Merrifield-Simmons指标最大的图.     

含有2个最大度点的树的极大独立集个数

研究了限制条件下图的极大独立集的计数问题.运用数学归纳法,给出了含有2个最大度点的树的极大独立集个数的最大值,同时刻画了取得最大值时的树.     

等邻集概念及其在部分标号图重构问题上的应用

在本文中,我们建立了等邻集概念,并推出了关于主子图的等邻集可标定定理(定理1)及等邻集的标定与邻接方阵的关系定理(定理2)。应用定理1及定理2证明了:由P阶图G的五个主子图G_1,G_2,G_3,G_4,G_5,(其中V_6,V_7,……,V_p己标号,其他V_i未标号)可重构G的结果(定理4)。这一结果比F.Harary和B.Manvel的结果更强。     

一类4-正则循环图的分数点色数

通过构造最大独立集和分数点着色 ,给出了一类 4 正则循环图的分数点色数     

D—圈图成为哈米顿图的一个新的充分条件

在本文中,我们给出了 D-圈图成为哈米顿图的一个新的充分条件。亦即证明了下列定理:如果 G 是 D-圈图,且对 G 的每个δ点独立集 S 都有|N(S)|>δ(p-1) /(δ+1) ,则 G 是哈米顿的。     

关于简单图的独立集多项式

定义了简单图的独立集多项式，讨论了图的独立集多项式与图的匹配多项式的关系，给出了图的独立集多项式的结构特征．     

在一类限定3-正则图中:β≥ n/3

G（V，E）是一个图。如果点集I是V的子集且＜I＞是空图，则称I是独立集，如果点集X是V子集且N[X]=V，则称X是控制集。如果点集I是V的独立集且又是控制子集，则称I是独立控制集，即极大独立集，β(G)=max{|I|I是G的独立集}，称β(G)是图G的独立数。在不发生混淆的情况下，用β表示图G的独立数，可以证明：在限定3－正则图中，β≥n/3，其中n是图的阶。     

一类单圈图的最大独立集的交

设G=(V(G),E(G))为有限简单图,X是V(G)的子集.若X中任意两个点不相邻则称X是独立集.用core(G)表示G的所有最大独立集的交.X的差是指X的顶点数与其邻集的顶点数之差.在G的所有顶点子集中,差最大的子集即为G的临界集.用ker(G)表示G的所有临界集的交.在图G中,core(G)?ker(G);当图G为二部图时,则core(G)=ker(G).本文刻画了一类单圈图G的core(G)=ker(G)的结构.     

用神经网络研究图的最大独立集问题

利用人工神经网络的原理．将图的最大独立集问题转换为人工神经网络的问题．对此网络进行了分析．并用计算机进行模拟．给出了不同规模的图的优化解．     

图的几乎哈密尔顿的新的充分条件

利用插点方法就κ-连通图G的独立集、本质独立集及G的部分平方图的独立集的邻域交，研究图的几乎哈密尔顿性，得到了关于图的几乎哈密尔顿的三个新的充分条件．     

几类图的独立约束数及独立加强数

利用归纳假设方法及图的独立数的一些定理，研究几类图——路、完全二分图、圈、树中的独立约束数及独立加强数．求出路、圈的独立约束数和独立加强数及完全二分图的独立约束数，并给出树独立加强数的界．