关于｛P2,Ci│i≥3｝—覆盖图

设Ｇ是一个图,若对于Ｇ的任意一边Ｇ都有｛Ｐ２,Ｃｉ│ｉ≥３｝－因子含有这条边,则称Ｇ是｛Ｐ２,Ｃｉ│ｉ≥３｝－覆盖图。本文给出连通非二分图Ｇ是｛Ｐ２,Ｃｉ│ｉ≥３｝－覆盖图的充要条件为任给Ｓ包含于Ｖ（Ｇ）,Ｖ（Ｇ）≠Ｓ≠ф有ｉ（Ｇ－Ｓ）≤│Ｓ│－１成立。     

关于一类(g,f)-3-覆盖图的判据

本文首先给出了(g,f)-3-覆盖图的定义,即一个图G称为(g,f)-3-覆盖图,如果G的任何三条边都属于它的一个(g,f)-因子；其次,黄光鑫曾先后给出了当g＜f时一个二部图分别是(g,f)-2-覆盖图和(g,f)-3-覆盖图的充分必要条件,在此基础上,本文进一步得到了,当g≤f时一个二部图G=(X,Y)是(g,f)-3-覆盖图的一个充分必要条件；最后,研究了f(X)=f(Y)的情形,得到了当f(X)=f(Y)时一个二部图G=(X,Y)是f-3-覆盖图的一个充分必要条件．     

无$K_{1,4}$子图的图的路覆盖

For a graph G, a path cover is a set of vertex disjoint paths covering all the vertices of G, and a path cover number of G, denoted by p(G), is the minimum number of paths in a path cover among all the path covers of G. In this paper, we prove that if G is a K_(1,4)-free graph of order n and σ_(k+1)(G) ≥ n-k, then p(G) ≤ k, where σ_(k+1)(G) = min{∑v∈S d(v) : S is an independent set of G with |S| = k + 1}.     

关于图的星形因子覆盖

如果图 G 的支撑子图 M 的每个分支都同构于{K_(1,1)K_(1,2,)…,K_(1,k}(k≥2)中的某个 K_(1,i),则 M(?)叫做 G 的星形因子。进一步,如果对于图 G 的每一条边都存在一个星形因子包含这条边,则称图 G 是星形因子覆盖的。本文给出了图是{P_2,P_3}一因子覆盖的充要条件,并证明了任意正则图均存在星形因子覆盖。     

图的{P4}-分解

一个图G的路分解是指一路集合使得G的每条边恰好出现在其中一条路上.记Pl长度为l-1的路,如果G能够分解成若干个Pl,则称G存在{Pl}—分解.关于图的给定长路分解问题主要结果有:(i)连通图G存在{P3}—分解当且仅当G有偶数条边(见[1]);(ii)连通图G存在{P3,P4}—分解当且仅当G不是C3和奇树,这里C3的长度为3的圈而奇树是所有顶点皆度数为奇数的树(见[3]).本文讨论了3正则图的{P4}—分解情况,并构造证明了边数为3k(k热∈Z且k≥2)的完全图Kn和完全二部图Kr,s存在{P4}—分解.     

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

设 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相似文献   

图的{P4}——分解

一个图G的路分解是指一路集合使得G的每条边恰好出现在其中一条路上．记Pl长度为l-1的路，如果G能够分解成若干个Pl，则称G存在{Pl}——分解，关于图的给定长路分解问题主要结果有：（i）连通图G存在{P3}-分解当且仅当G有偶数条边（见[1]）；（ii）连通图G存在{P3，P4}-分解当且仅当G不是C3和奇树，这里C3的长度为3的圈而奇树是所有顶点皆度数为奇数的树（见[3]）．本文讨论了3正则图的{P4}--分解情况，并构造证明了边数为3k（k∈Z且k≥2）的完全图Kn和完全二部图Kr,s存在{P4}-分解.     

关于k—覆盖图的一些新结果

本文给出了一个图G是k-覆盖图的若干充分条件．     

关于图的最小覆盖算法

本文就数学建模课的教学过程中 ,在“图的方法建模”一章中 ,关于图的最小覆盖法提出启发式算法 .用书中所给方法推出一个反例 ,分析了其产生错误的原因 ;通过对图的最小覆盖的概念的理解、结合分析图的关联矩阵的特点 ,给出了图的最小覆盖的启发式算法 .     

连通的K_{n}-残差图

m-K_{n}-残差图是由P. Erd\"{o}s, F. Harary和M. Klawe等人提出的, 当m=1时, 他们证明了当n\neq1,2,3,4时, K_{n+1}\timesK_{2}是唯一的具有最小阶的连通的K_{n}- 残差图. 首先得到了m-K_{n}-残差图的重要性质, 同时证明了当n=1,2,3,4时, 连通K_{n}-残差图的最小阶和极图, 其中当n=1,2时得到唯一极图; 当n=3,4时, 证明了恰有两个不同构的极图, 从而彻底解决连通的K_{n}-残差图的最小阶和极图问题. 最后证明了当n\neq1,2,3,4时, K_{n+1}\timesK_{2}是唯一的具有最小阶的连通的K_{n}-残差图.     

f—因子覆盖的图

设G为图,f是定义在V(G)上的正整数值函数。称图G的支撑子图F为f-因子如果d_(?)(x)-f(x),x∈V(G).称图G是f-因子覆盖的如果G的每条边包含在一个f-因子中.本文给出了一个图是f-因子覆盖的图的充要条件,其结果推广了C.H.C.Little et al.[1]的1-因子覆盖定理。     

关于(g,f)-2-消去图

一个图G称为一个(g,f)-2-消去图,如果G的任何两条边不属于它的一个(g,f)-因子.本文给出了当g＜f时一个图是(g,f)-2-消去图的一个充要条件.     

分数(g,f)-因子覆盖图

一个图称为分烽（g,f)- 因子覆盖图，如果G中的任何一条边e都包含在一个分数（g,f)- 因子中，并且满足h(e)=1，其中h是分数（g,f)- 因子的导出函数。本文给出了一个图是分数（g,f)- 因子覆盖图的充要条件。     

关于群图的{Cni∈I}—因子

设Cn是长度为n(n≥3)的圈，如果图G的生成子图F的每个分支都同构于圈集{Cni∈I}的一个元素，列F称为G的一外{Cni∈I}—因子，若G是其边不重{Cni∈I}—因子之并，则G称为可—{Cni∈I}因子化，1988年，M．-J．P．Ruiz在[1]中给出了有限简单连通无向群图，有Cn—因子的充分条件及可{Ca,…Cp}—因子他的充分条件，然而，Ruiz的结果是本相应结果的特例。     

图P2×Cn的全符号{k}-控制数北大核心

给出了图P2×Cn的全符号{k}-控制数,该结果纠正了Bohdan Zelinka(2001)的一个错误.     

2-弧传递图的正则覆盖:研究综述

图X的一个2-弧,指的是X的3个不同的点构成的序列(v0,v1,v2),使得(v0,v1)和(v1,v2)均为弧.图X称为是2-弧传递的,如果全自同构群Aut(X)在X的所有2-弧组成的集合上的作用是传递的.如果存在从X的顶点集到Y的顶点集的一个满射p,使得p限制在每个点的邻域上是一个双射,则称X为Y的一个覆盖,且称p...     

分数(g,f,m)-覆盖图的充要条件

G是一个图,g和f是两个定义在V(G)上的非负整数值函数,并且对任意的x∈V(G),满足g(x)≤f(x).称图G是分数(g,f,m)-覆盖图,如果存在图G的分数(g,f)-因子G[F_h]满足对任意的e∈E(H)有h(e)=1,其中H是图G的m条边的子图.证明了一个图是分数(g,f,m)-覆盖图的充要条件,并得到了几个推论.     

连通的三重K_{n}-残差图

Erd\"{o}s P, Harary F和Klawe M研究了K_{n}-残差图, 并对连通的m-K_{n}-残差图提出了一些结论和猜想. 利用容斥原理以及集合的运算性质等方法, 研究了连通的3-K_{n}-残差图, 得到当顶点最小度为n时, 3-K_{n}-残差图最小阶的计算公式以及相应的唯一极图. 当n=2时, 得到最小阶为11以及相应的极图; 当n=3时, 得到最小阶为20并找到两个不同构的极图, 不满足Erd\"{o}s等提出的结论; 当$=4时, 得到最小阶为22及相应的极图; 当n=8, 可以找到两个不同构的3-K_{8_{}}-残差图, 不满足Erd\"{o}s等提出的结论; 最后证明了当n=9,10时, 最小阶分别为48和52以及相应的唯一极图, 验证了Erd\"{o}s等在文献~(Residually-complete graphs [J].Annals of Discrete Mathematics, 1980, 6: 117-123) 中提出的结论.     

一个关于图是[a,b;n]-均匀的度条件

设t,a,b和n为整数且1≤a＜b,t≥3以及n≥1.如果G的导出子图不含有K1,t,则该图G称为K1,t-无爪图.如果对于图G中含有n条边的任意匹配M,都在G中有[a,b]-因子F包含M以及在G中有另一个[a,b]-因子F'不包含M,则图G称为[a,b;n]-均匀图.给出了K1,t-无星图G是[a,b;n]-均匀图的度条件.进一步,指出本文中的结果在某种意义上说是最佳的.     

关于图的(g,f)-因子分解

设G是一个图,g和f是定义在图G的顶点集V(G)上的两个非负整数值函数且g＜f.图G的一个(g,f)-因子是G的一个支撑子图F,使对所有的x∈V(G)有g(x)≤d_F(x)≤f(x).若G本身是一个(g,f)-因子,则称G是一个(g,f)-图.若G的边能分解成一些边不交的(g,f)-因子,则称G是(g,f)-因子可分解的.本文给出图G是(g,f)-因子可分解的一个充分条件.