消去图、覆盖图和均匀图的若干结果

设 G是一个图 ,g,f是定义在图 G的顶点集上的两个整数值函数 ,且g≤f.图 G的一个 ( g,f) -因子是 G的一个支撑子图 F,使对任意的 x∈V( F)有g( x)≤ d F( x)≤ f ( x) .文中推广了 ( g,f) -消去图、( g,f ) -覆盖图和 ( g,f) -均匀图的概念 ,给出了在 g相似文献   

书本图Bm的协调和相继标号

本文给出了书本图Ｂ２ｍ的ｍ种不同的相继标号和Ｂ４ｍ＋１的ｍ种不同的相继标号。因而，书本图Ｂｍ是相继图的充分条件为：ｍ＞１且ｍ≠（３ｍｏｄ４）。这一条件也是书本图Ｂｍ是协调图的充要条件。     

关于n-可扩图的一些结果

本文讨论了关于m-可扩图的两个极值问题；并考查了下述图类的n-可扩性；正则偶图，单位区间图和分裂图。     

Bubble-sort图和Modified Bubble-sort图的自同构群

Bubble-Sort图和Modified Bubble-Sort图是两类特殊的Cayley图,由于其在网络构建中的应用而受到广泛关注.本文完全确定了这两类图的自同构群.     

(g,f)-消去图的若干充分条件

设 G是一个图 ,用 V(G)和 E(G)表示它的顶点集和边集 ,并设 g和 f是定义在 V(G)上的两个整数值函数且 g 相似文献   

几族3-优图

一个图 G中含有的三个结点的导出连通子图的个数 S3( G)在网络可靠性中起着重要作用 .在同点数同边数图类中具有最大 S3( G)的图称为 3-优图 ,它所代表的网络是点故障概率接近 1时的最可靠网络 .本文在已有的结果上进一步证明补图为 a K3∪ b K2 ∪ K1和 a K3-x的图分别是各自图类中唯一的 3-优图 ;补图为 a K3∪ ( b-1 ) K2 ∪ 2 K1和 ( a-1 ) K3∪ b K2 ∪ P3的图是该图类中仅有的两个 3-优图 .     

一般图的哈密顿图的研究进展

1991年刘振宏和李明楚在南京大学召开的首届哈密顿图研讨会的综述文章中说"要给出一个一般图具有哈密顿圈的充分条件是一件非常不容易的事"。因哈密顿图是含哈密顿圈的图类,如此哈密顿图主要有六个方向:哈密顿圈、哈密顿连通、泛圈图、点泛圈图、泛连通图、最短路径泛圈图。本文中,我们就给出一般图的这些领域新进展的小综述。     

One-step模糊图及相关的分解定理

主要研究一种特殊的模糊图(即one-step模糊图)的性质。提出了one-step模糊图、Hamiltonian模糊图、r-正则模糊图、二部模糊图、连通模糊图等概念,给出了强one-step Hamiltonian模糊图、强one-step r-正则模糊图、强one-step二部模糊图、强one-step连通模糊图的构造、强one-step模糊图在笛卡尔积、合成、补运算下的的简易表达式、one-step模糊图的分解定理以及强one-step模糊图在笛卡尔积运算下保持不变的一些性质,证明了任意模糊图可以分解为one-step模糊图。     

（mg＋m—1,mf—m＋1）—图的（g,f）—因子

本文证明了（ｍｇ＋ｍ－１,ｍｆ－ｍ＋１）－图具有一些特殊的（ｇ,ｆ）－因子,从而推广到了关于（ｇ,ｆ）－覆盖图和（ｇ,ｆ）－消去图的有关结果,有助于进一步研究（ｍｇ＋ｍ－１,ｍｆ－ｍ＋１）－图的正交因子分解问题。     

灯笼图的奇优美标号

提出了灯笼图、多向灯笼图、复杂灯笼图,研究了它们的奇优美性,证明灯笼图是二分奇优美图、超级边魔幻图和超级反魔幻图.     

图的局部k限制边连通性及最优性

首先研究图的局部k限制边连通性问题和局部λ_k-连通图的存在性问题.然后研究图的局部λ_k最优性,并且应用邻域条件得到了一个保证图局部λ_k最优的充分条件.     

C2(4,k) 中的强支撑可迹图

设2≤h≤3,l0,k≥0是整数,C_h(l,k)是由h-边连通简单图组成的集合,图G∈C_h(l,k)当且仅当对图G的任意一个二边割或三边割X,图G-X的每个分支都至少有︱V(G)-k︱/l个点.设e=u_1v_1和e'=u_2v_2是图G的两条边.若e≠e',G(e,e')是将图G中的边e=u_1v_1和e'=u_2v_2分别用路u_1v_ev_1和u_2v_e'v_2替换得到的图(其中,v_e,v_e'是不在V(G)中的两个新的点).若e=e',G(e,e')是将图G中的边e=u_1v_1用路u_1v_ev_1替换得到的图,也记作G(e).若对任意的e,e'∈E(G),G(e,e')都有支撑(v_e,v_e')迹,则称图G是强支撑可迹的.作者证明了,若图G∈C_2(4,k)且|V(G)|5k,则要么图G是强支撑可迹图,要么存在e,e'∈E(G),使得G(e,e')可以收缩成一个有限图类F中的图.当k=4时,F被完全确定了.     

紧图的两个结果及其应用

双随机矩阵有许多重要的应用, 紧图族可以看作是组合矩阵论中关于双随机矩阵的著名的Birkhoff定理的拓广,具有重要的研究价值． 确定一个图是否紧图是个困难的问题,目前已知的紧图族尚且不多.给出了两个重要结果：任意紧图与任意多个孤立点的不交并是紧图;任意紧图的每一个顶点上各增加一条悬挂边的图是紧图． 利用这两个结果,从已知紧图可构造出无穷多个紧图族．     

给定阶数的简约单圈图的秩集(英文)

图的秩定义为其邻接阵的秩.如果一个连通图中不同顶点的邻域是不同的,我们称该图是简约图.本文证明有n个顶点简约单圈图的秩r满足:若r是偶数,则2n/3≤r≤n;若r是奇数,则(2n+5)/3≤r≤n.同时我们给出有偶数秩r和阶数3r/2或奇数秩r和阶数(3r-5)/2极大简约单圈图的刻画.     

奇图的匹配可扩性

设G是一个图,n,k和d是三个非负整数,满足n+2k+d≤|V(G)|-2,|V(G)|和n+d有相同的奇偶性.如果删去G中任意n个点后所得的图有k-匹配,并且任一k-匹配都可以扩充为一个亏d-匹配,那么称G是一个(n,k,d)-图.Liu和Yu[1]首先引入了(n,k,d)-图的概念,并且给出了(n,k,d)-图的一个刻划和若干性质. (0,k,1)-图也称为几乎k-可扩图.在本文中,作者改进了(n,k,d)-图的刻划,并给出了几乎k-可扩图和几乎k-可扩二部图的刻划,进而研究了几乎k-可扩图与n-因子临界图之间的关系.     

（a,b,k）—临界图

设Ｇ是一个图且设ａ，ｂ是非负整数，ａ〈ｂ。如果消去Ｇ的任意ｋ个顶点剩下的图有〔ａ，ｂ〕因子，则称图Ｇ是（ａ，ｂ，ｋ）－临界图。本文给出了一个图是（ａ，ｂ，ｋ）－临界图的一个充分必要条件。讨论了该条件的一些应用，研究了（ａ，ｂ，ｋ）－临界图的性质。     

n圈中辐图的团覆盖数和团划分数

本主要讨论Petersen图的一类推广图－n圈中辐图的团覆盖数和团划分数,由此得出该图的团覆盖数和团划分数相等的结论,同时给出了其在不同情况下的计算公式。     

平面对偶图哈密顿性的一个充分条件

提出了平面单图的对偶图是哈密顿图的一个充分条件     

正则图的变换图的谱

设G是一个图,类似全图的定义,可以定义G的8种变换图.如果G是正则图,那么图G的变换图的谱都可以由图G的谱计算得到.     

探针区间图和STS-探针区间图的刻划

该文首先引入了探针区间序来刻划探针区间图;接着给出STS-探针区间图的探针区间完备的一种构造方法,并借此得到二部图G是相对于给定顶点划分的STS-探针区间图的一个充要条件;同时也说明了STS-探针区间图其实就是其他文献中被独立研究的凸二部图.最后基于前面给出的STS-探针区间图的刻划结果提供了两种简单的O(V E)时间的STS-探针区间图的判别算法.