无爪图中具有指定长度的路因子

在无爪图G中,设σ2(G)表示不相邻顶点度和的最小值. 令|V(G)|=n=∑ki=1ai,ai6,1ik,并且σ2(G)n+k-1,证明了对于图G中任意的k个顶点v1,v2,…vk, 都存在点不相交的路P1,P2,…Pk,使得对于1ik,都有|V(Pi)|=ai并且vi是路Pi的一个端点.     

立方图中的路因子和圈因子

给定连通图集合Φ,对图G的生成子图F,如果F的每个分支都同构于集合Φ的一个元素,则F被称为G的Φ-因子.最近Kawarabayashi 等证明了:2-连通立方图有一个{Cn|n≥4}-因子和{pn|n≥6}-因子,其中Cn表示阶为n的圈,Pn表示阶为n的路.Kano等给出了每一个阶至少为8的立方偶图有{Cn|n≥6}-因子和{pn|n≥8}-因子的结论,并且提出猜想:阶至少为6的3-连通立方图有{Cn|n≥5}-因子和{pn|n≥7}-因子.现给出这个猜想的证明.     

半无爪图中的路因子

证明了如果G是一个半无爪图且它的最小度不小于d,那么G有一个路因子满足每条路的顶点数不小于d+1。     

关于图的路因子分解

主要结果是：如果Ｐ＝（２ｎ）ｍ，ｍ １，则Ｋｙ可Ｐ２ｎ－因子分解，其中Ｐ２ｎ表示具有２ｎ个顶点的无向图。     

最长路原理与图中的路和图

设Ｐ＝ｖ０ｖ１…ｖｋ（其中ｖｋ＝ｙ为图Ｇ中一条最长ｙ－路，即以ｙ为络点的路中最长者，那私Ｎ（ｖ０）包函于Ｖ（Ｐ），且对ｖｊ∷Ｎ（ｖ０），ｖｊ－１ｖｊ－２…ｖ０ｖｖｊ＋１…ｖｋ也是最长ｙ－路，利用该简单原理证明：对于２－连通非Ｈａｍｉｌｔｏｎ图Ｇ的任一顶点ｙ，存在某最长ｙ－路Ｐ（ｘ，ｙ）使ｄ（ｘ）较大。据此直接推出关于周长的范更华定理等重要结果。     

与路2—正交的（g,f）—因子分解

设ｇ和ｆ分别是定义在图Ｇ的机点集合Ｖ（Ｇ）上的整数值函数且对每个ｘ∈Ｖ（Ｇ）有４≤ｇ（ｘ）≤ｆ（ｘ）。证明了若Ｇ是一个（ｍｇ＋ｍ－１,ｍｆ－ｍ＋１）－图,则对Ｇ中任意给定的长为２ｍ的路Ｐ,Ｇ有一个（ｇ,ｆ＿－因子分解２－正交于Ｐ。     

图的路覆盖数的上界

设G是简单图。记ρ(G)为覆盖图G所需路数的最小值。本文证明了ρ(G)≤[2n/3];且若G是连通图,则ρ(G)≤[3n/5]。     

一般图的不交路划分问题

给定一个阶为n的简单图G=(V；E)，其中α(G)≥4，及1个正整数k≥2，考虑在领域条件下G划分成k条点不交路的问题，并得到下面的结果：对G中任何4个独立点x1，x2，y1，y2，满足领域条件，1NG(x1)∪NG(x2){ }NG(y1)∪NG(y2)1≥n-k-1，则要么G能划分成k条点不交的路，要么G属于一类例外图G′。     

2-连通图中点不交路的划分问题

给定一个阶为n的2-连通图G=(V;E)及一个正整数k,考虑在邻域并条件下G被分成k条点不交路的问题,得到下面的结果,对G中任何四个独立点x1,x2,y1,y2∈V,满足|NG(x1)∪NG(x2)| |NG(y1)∪NG(y2)|n-k,则G能被分划分k条点不交的路.     

反d-退化图中的点不交3-圈

如果图G的补图(-overG)是d-退化图,则称图G是反d-退化图。证明了当|G|=3k且δ(G)≥k≥26d时,反d-退化图G包含k个点不交的3-圈,其中d≥2。     

关于完全3部图的色唯一性

文章设P(G,λ)是图G的色多项式,若对于任意与图G的色多项式相等(P(G,λ)=P(H,λ))的图H都与图G同构(G≌H),则称图G是色唯一图;通过比较3部图的4色类的划分数证明,如果4≤v+2≤k≤2v,n>(k-1)2/4,则完全3部图K(n,n+v,n+k)是色唯一图。     

一种用4-圈和8-圈对二分图的划分

证明了如果一个平衡二分图G包含4k个点,k≥2,并且对G中每一对满足x∈V₁,y∈V₂的不相邻顶点x和y成立d(x)+d(y)≥2k+1, 则G包含k-2个4-圈和一个8-圈,并且这k-1个圈点不相交。     

带限制条件的两个平面图同时嵌入的交叉数

考虑两个平面图, 一个染成红色, 另一个染成绿色.两个图同时胞腔嵌入平面时,在一定的限制条件下, 红色的边与绿色的边会相交. 称这样的交点为交叉点.在所有的嵌入方式中交叉点的最小个数称为交叉数.本文利用图的划分和最小边割集,把这种交叉数问题转化为一类整数规划问题,得出了一些结果.     

均衡二部图中含指定顶点独立6-圈的个数

给出了均衡二部图具有含指定顶点的k个独立圈,其中恰好含s个4-圈和k-s个6-圈的最小度条件。     

有负权时有向图全路径算法研究

有向图有负权路径求解问题比较常见,但求所有可达路径的算法却见之甚少。本文在以前提出的一种有向图无负权所有可达路径搜索算法的基础上,提出一种先将有负权问题转换成无负权问题,进而用无负权算法求解之的方法。     

最小最大路划分的一个启发式算法

首先证明了最小最大路划分问题是困难的,然后利用二分算法给出了特殊情形下的最优算法,最后给出了满足三角不等式的图上的一个启发式算法.     

完全图和完全多部图的Mycielski图的星全染色

讨论了完全二部图、完全图和完全多部图的Mycielski图的星全染色问题,得到了它的星全色数.