一类free图极小零度的图结构

设G是n阶简单图,G的特征值零的重数称为G的零度。给出了一类free图当其零度达到下界0时的一类图结构,并证明图邻接矩阵具有A(G)=〔0DT DC〕形式时其零度达到下界。

泛圈的K_(1.3)-Free图

在n阶的2-连通的K_(1.3)-Free中,若对任何3个相互无关的独立点{x,y,z)总有:d(x)+d(y)+d(z)≥n-2.则除去某些小阶的例外图之外,G是泛围图。

K_(1.3)—Free图成为哈米顿的一个邻域并条件

在本文中,我们给出下列定理:设G为阶是n≥3的2—连通,K_(13)—free图且满足NC(G)≥n—δ—2。则G为哈米顿的,这里NC(G)=min{|N(u)N(v)|E}。

K_(1.3)—Free图成为可遍历的一个邻域并条件

在本文中,我们给出了下列定理:设G是阶为n≥3的连通K_(13)—Free图且NC(G)≥n—δ—2。则G是可遍历的。

K_（1，r）－Free图的生成树及其算法

证明了任一连通的Ｋ（１，ｒ）－Ｆｒｅｅ图都有最大度小于等于ｒ的生成树，并建立了算法。

K_（1，r）－free图的次限制树多项式算法

设Ｇ＝（Ｖ，Ｅ）为一连通图，ｄ＞０整数．Ｇ中存在生成树Ｔ，使得Δ（Ｔ）小于ｄ吗？这一问题已被证明是ＮＰ－完全的，故不太可能有多项式解法．本文证明了当Ｇ是Ｋ１，ｒ－ｆｒｅ时，则有Ｏ（ｎ２）的算法求出Ｇ的生成树Ｔ，使Δ（Ｔ）≤ｒ。

一类free图极大零度的图结构

设G是n阶简单无向图,G的特征值为零的重数被称G的零度。本文给出了一类free图,当3V??且当其零度达到极大值2n?V时的图结构,并证明了当????0 00A GC?形式时,其零度达到极大值。

不含2K_1+K_2和C_4作为导出子图的图的色数(英文)

设图G不含与2K_1+K_2同构的导出子图,并且不含导出4-圈,通过对该图类独立数的讨论,刻画出它的结构,从而得到该图类色数与团数有关的线性的上界.

（K1，4；2）-图的闭包和周长

针对（K1,4；2）-图这一新的图类，证明了以下结论：1）设G是δ≥5且K1∨P4-free的（K1,4；2）-图，则c（G）=c（cl（G））；2）设G是δ≥5且T3-free的（K1,4；2）-图，则c（G）=c（cl（G））．

(K_(1,4);2)-图的3-闭包中的路

对(K1,4;2)-图,证明它的3-闭包的一个性质。G为{K1∨P5,T3}-free或K1∨P4-free的(K1,4;2)图,x,a,b为G中不同三点,x为G中局部3-连通的适宜点,G′由G在点x局部完备所得。若G′中有长为l的(a,b)-路,则G中有长为l的(a,b)-路。

图的点强全染色

图G(V,E)的正常k—全染色f叫做G(V,E)的k—点强全染色,当且仅当对任意的w∈V(G),N[w]中元素染不同颜色,其中N[w]={x|wx∈E(G)}∪{w}.并称XvTs(G)=min{k|存在G的k—点强全染色}为图G(V,E)的点强全色数.本文研究了K4-minor free图和外平面图的点强全色数.

Spanning 3-ended trees in k-connected K_(1,4)-free graphs

A tree with at most m leaves is called an m-ended tree.Kyaw proved that every connected K1,4-free graph withσ4(G)n-1 contains a spanning 3-ended tree.In this paper we obtain a result for k-connected K1,4-free graphs with k 2.Let G be a k-connected K1,4-free graph of order n with k 2.Ifσk+3(G)n+2k-2,then G contains a spanning 3-ended tree.