关于图的（g,f）—因子分解的一些新结果

本文讨论图的（ｇ，ｆ）－因子分解问题，推广了文「１」关于图的因子分解的理论，改进了文「２」的一些结果，给出了一个图Ｇ是（ｇ，ｆ）－可因子化的若干充分条件。     

关于K_（1，r）－free图的连通因子

本文证明了每个连通的Ｋ１，ｒ－ｆｒｅｅ图Ｇ，如果有［ｆ，ｇ］－因子Ｆ，则它就有包含Ｆ的［ｆ，ｇ＋ｒ－１］连通因子．     

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

设Ｇ是一个图，ｇ（ｘ）和ｆ（ｘ）是定义在图Ｇ的顶点集上的两个整数值函数且ｇ≤ｆ．图Ｇ的一个（ｇ，ｆ）－因子是Ｇ的一个支撑子图Ｆ使对任意的ｘ∈Ｖ（Ｆ），有ｇ（ｘ）≤ｄＦ（ｘ）≤ｆ（ｘ）．如果图Ｇ的边集能划分为若干个边不相交的（ｇ，ｆ）－因子，则说图Ｇ是（ｇ，ｆ）－可因子化的．本文研究了图的（ｇ，ｆ）－可因子化的问题，给出了一个图Ｇ是（ｇ，ｆ）－可因子化的若干充分条件．     

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

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

图的（g，f）－因子和因子分解

设Ｇ是一个图，ｇ，ｆ是定义在图Ｇ的顶点集上的两个整数值函数且图Ｇ的一个（ｇ，ｆ）－因子是Ｇ的一个支撑子图Ｆ使对任意的ｘ∈Ｖ（Ｆ）有本文给出了一个图（ｇ，ｆ）－可因子化的若干充分条件和一个图是（ｇ，ｆ）－消去图的充分必要条件，并研究了这些条件的应用。     

图的（g，f）－因子和因子分解

设Ｇ是一个图，ｇ，ｆ是定义在图Ｇ的顶点集上的两个整数值函数且图Ｇ的一个（ｇ，ｆ）－因子是Ｇ的一个支撑子图Ｆ使对任意的ｘ∈Ｖ（Ｆ）有本文给出了一个图（ｇ，ｆ）－可因子化的若干充分条件和一个图是（ｇ，ｆ）－消去图的充分必要条件，并研究了这些条件的应用。     

复合图的1－因子分解

本文研究了复合图１－因子分解问题，给出了复合图可１－因子分解的几个充分条件．设图Ｇ和Ｈ都是正则因，那么Ｇ和Ｈ的复合图Ｇ［Ｈ］可１－因子分解，如果Ｇ和Ｈ满足下列三个条件之一：（１）Ｇ可１－因子分解；（２）Ｇ至少有　１－因子，Ｈ为偶阶正则图［Ｖ（Ｈ）｜≥２；（３）Ｇ可以分解为一些１－因子和２－因子之并，Ｈ为偶阶正则图且至少有ｍａｘ｛０，△（Ｈ）－４｝个１－因子．     

图中具有某种性质的子图

设ｇ和ｆ是定义在图Ｇ的顶点集合Ｖ（Ｇ）上的整数值函数且对每个ｘ∈Ｖ（Ｇ）都有０≤ｇ（ｘ）≤ｆ（ｘ）且ｇ（ｘ）和ｆ（ｘ）为偶数。本文证明了：若Ｇ是一个（ｍｇ＋ｋ－１,ｍｆ－ｋ＋１）－图,１≤ｋ≤ｍ,Ｈ是Ｇ中一个给定的有ｋ条边的子图,则Ｇ存在一个子图Ｒ使得Ｒ有一个（ｇ,ｆ）－因子分解与Ｈ正交。     

图的（g＜f）－因子

设Ｇ是一个图，ｇ和ｆ是定义在图Ｇ的顶点集上的两个整数值函数且ｇ＜ｆ．本文给出了过图的每条边有一个（ｇ，ｆ）－因子的新的简单的判断准则，并研究了它的应用。从而得到了一些关于图有（ｇ，ｆ）－因子的新的充分条件，推广了若干已有的结果．     

具有与任意图正交的(g,f)-因子分解的子图

设ｇ和ｆ分别是定义在图Ｇ的顶点集合Ｖ（Ｇ）上的整数位函数且对每个ｘ∈Ｖ（Ｇ）有０≤ｇ（ｘ）≤ｆ（ｘ）．证明了：若Ｇ是一个（ｍｇ＋ｋ,ｍｆ－ｋ）－图,１≤ｋ＜ｍ,Ｈ是Ｇ中一个给定的有ｋ条边的子图,则Ｇ有一个子图Ｌ使得Ｌ有一个（ｇ,ｆ）－因子分解与Ｈ正交．     

关于图是(g,f,n)-临界图的充分条件

设G是一个图. 设g和f是两个定义在V(G)上的整值函数使得对V(G)所有的顶点x有g(x)f(x). 图G被称为(g,f,n)-临界图,如果删去G的任意n个顶点后的子图都含有G的(g,f)-因子. 本文给出了图是(a,b,n)-临界图几个充分条件. 进一步指出这些条件是最佳的. 例如,如果对V(G)所有的顶点x和y都有g(x)＜f(x), n+g(x)dG(x)和g(x)/(dG(x)-n)f(y)/dG(y),则G是(g,f,n)-临界图.     

Acylindrical accessibility for groups

We define the notion of acylindrical graph of groups of a group. We bound the combinatorics of these graphs of groups for f.g. freely indecomposable groups. Our arguments imply the finiteness of acylindrical surfaces in closed 3-manifolds [Ha], finiteness of isomorphism classes of small splittings of (torsion-free) freely indecomposable hyperbolic groups as well as finiteness results for small splittings of f.g. Kleinian and semisimple discrete groups acting on non-positively curved simply connected manifolds. In order to get our accessibility for f.g. groups we generalize parts of Rips' analysis of stable actions of f.p. groups on real trees to f.g. groups. The concepts we present play an essential role in constructing the canonical JSJ decomposition ([Se1],[Ri-Se2]), in obtaining the Hopf property for hyperbolic groups [Se2], and in our study of sets of solutions to equations in a free group [Se3]. Oblatum 30-IV-1992 & 1-X 1996     

完全-因子和(g,f)-对等图

若图的因子F的每一个分支都是完全图,则称F为完全-因子.本文研究了完全-因子F和(g,f)-对等图之间的关系,给出了有完全-因子F的图是(g,f)-对等图、f-对等图及k-对等图的关于F的分支的若干充分条件,并指出定理中的条件在一定意义上是最可能的,从而推广了李建湘等人的有关结果.     

Claw-free graphs with strongly perfect complements. Fractional and integral version. Part I. Basic graphs

Strongly perfect graphs have been studied by several authors (e.g. Berge and Duchet (1984) [1], Ravindra (1984) [12] and Wang (2006) [14]). In a series of two papers, the current paper being the first one, we investigate a fractional relaxation of strong perfection. Motivated by a wireless networking problem, we consider claw-free graphs that are fractionally strongly perfect in the complement. We obtain a forbidden induced subgraph characterization and display graph-theoretic properties of such graphs. It turns out that the forbidden induced subgraphs that characterize claw-free graphs that are fractionally strongly perfect in the complement are precisely the cycle of length 6, all cycles of length at least 8, four particular graphs, and a collection of graphs that are constructed by taking two graphs, each a copy of one of three particular graphs, and joining them in a certain way by a path of arbitrary length. Wang (2006) [14] gave a characterization of strongly perfect claw-free graphs. As a corollary of the results in this paper, we obtain a characterization of claw-free graphs whose complements are strongly perfect.     

Claw-free graphs with strongly perfect complements. Fractional and integral version, Part II: Nontrivial strip-structures

Strongly perfect graphs have been studied by several authors (e.g., Berge and Duchet (1984) [1], Ravindra (1984) [7] and Wang (2006) [8]). In a series of two papers, the current paper being the second one, we investigate a fractional relaxation of strong perfection. Motivated by a wireless networking problem, we consider claw-free graphs that are fractionally strongly perfect in the complement. We obtain a forbidden induced subgraph characterization and display graph-theoretic properties of such graphs. It turns out that the forbidden induced subgraphs that characterize claw-free graphs that are fractionally strongly perfect in the complement are precisely the cycle of length 6, all cycles of length at least 8, four particular graphs, and a collection of graphs that are constructed by taking two graphs, each a copy of one of three particular graphs, and joining them in a certain way by a path of arbitrary length. Wang (2006) [8] gave a characterization of strongly perfect claw-free graphs. As a corollary of the results in this paper, we obtain a characterization of claw-free graphs whose complements are strongly perfect.     

Halin-图的邻强边染色

图G(V,E)的正常κ-边染色f叫做图G(V,E)的κ-邻强边染色当且仅当任意uv∈E(G)满足f[u]≠f[v],其中,f[u]={f(uw)|uw∈E(G)},称f是G的κ-临强边染色,简记为κ-ASEC.并且x′_as(G)=min{k|κ-ASEC of G}叫做G(V,E)的邻强边色数.本文研究了△(G)≥5的Halin-图的邻强边色数.     

一个关于(k;g)-笼的猜想的证明

(k;g) -笼是指具有围长 g的 k-正则图中那些顶点数最小的图 .文 [2 ]中有下面的猜想 :设 G为一个 ( k;g) -笼 ,则它的每一个 g-圈 C是不可分离的 ( nonseparating) ,也就是说 ,对 G中任意的 g-圈 C,G- C仍是连通的 .对于偶数 g,[2 ]已给出了此猜想的证明 .本文中 ,证明 :对于奇数 g,此猜想也是正确的 .     

最大度不小于5的外平面图的邻强边染色

图G(V,E)的一k-正常边染色叫做k-邻强边染色当且仅当对任意uv∈E(G)有,f[u]≠f[v],其中f[u]={f(uw)|uw∈E(G)},f(uw)表示边uw的染色.并且x'as(G)=min{k|存在k-图G的邻强边染色}叫做图G的图的邻强边色数.本文证明了对最大度不小于5的外平面图有△≤x'as(G)≤△ 1,且x'as(G)=△ 1当且仅当存在相邻的最大度点.     

图在三种约束条件下的正常全染色

设f:V(G)∪E(G)→{1,2,…,k}是简单图G的一个正常k-全染色.令C(f,u)={f(e):e∈N_e(u)},C[f,u]=C(f,u)∪{f(u)},C_2[f,u]=C(f,u)∪{f(x):x∈N(u)}∪{f(u)}.N(u)表示顶点u的邻集,N_e(u)表示与顶点u的相关联的边的集合.令C[f;x]={C(f,x);C[f,x];C_2[f,x]},对任意的xy∈E(G),G[f;x]≠C[f;y]表示C(f,x)≠C(f,y),C[f,x]≠C[f,y],C_2[f,x]≠C_3[f,y]同时成立.对任意的边xy∈E(G),如果有C[f;x]≠C[f;y]成立,则称f是图G的一个k-(3)-邻点可区别全染色(简记为(3)-AVDTC).图G的(3)-邻点可区别全染色中最小的颜色数叫做G的(3)-邻点可区别全色数,记为x_((3)as)″(G).研究了联图,完全二部图的(3)-邻点可区别全染色,得到了它们的(3)-邻点可区别全色数.