线图泛圈性的一个充分条件

本文证明了如果Ｇ是２连通线图,Ｇ不是圈,ｎ＝｜Ｖ（Ｇ）｜≥９且Ｇ的每个同构于Ａ的导出子图都满足（ａ１,ａ２）,则Ｇ是泛圈图     

一类泛连通无爪图

本文证明了如果Ｇ是３连通无爪图，且Ｇ的每个导出子图Ａ，Ａ＋都满足（ａ１，ａ２），则Ｇ是泛连通图（除了当ｕ，ｖ∈Ｖ（Ｇ），ｄ（ｕ，ｖ）＝１时，Ｇ中可能不存在（ｕ，ｖ）－ｋ路外，这里２≤ｋ≤４）．     

一类Hamilton图

本文证明了：如果Ｇ是２连通无爪图且Ｇ中不含同构于Ｚ３．Ｄ的导出子图．则Ｇ是Ｈａｍｉｌｔｏｎ图（除Ｇ≌Ｇ１．Ｇ≌Ｇ２外）。     

图的导出森林2-划分

对一个给定的简单图Ｇ，是否存在Ｖ（Ｇ）的一个２－划分（Ｖ１，Ｖ２）使得每个导出子图Ｇ［Ｖｉ］为森林？称该问题为导出森林２－划分问题．本文证明了对最大度为５的图该问题是ＮＰ－完全的，而对最大度≤４的图该问题多项式时间可解．     

Hamilton图的特定生成了图问题的反例

［１］定理３断言：一个Ｈａｍｉｌｔｏｎ图Ｇ必存在仅有ｐ条桥的相间偶圈，如果相间偶圈的边中有边在Ｇ的ｐ个不连通初等子圈上（ｐ≥２）。本的反例表明上述结论是错的，从而［１］中关于Ｐｅｔｅｒｓｏｎ图不是Ｈａｍｉｌｔｏｎ图的证明也不成立。     

图的最大亏格与2-因子

图Ｇ的一个２因子Ｆ就是Ｇ的这样一个支撑子图，使其任何节点ｖ∈Ｖ的次ｄＦ（ｖ）＝２．易见，Ｇ的每个２因子均为无公共节点的圈之并．若Ｆ的每个圈的长均为３（或４），则称Ｇ含有一个三角形（或四边形）２因子．Ｍ．ｋ∨ｏｖｉｅｒａ［５］得到了含有三角形２因子的３－正则图的最大亏格．本文在３－正则图上，引进了扩张运算和讨论了与最大亏格和Ｂｅｔｉ亏数之间的关系．利用这些运算，得到了所有含四边形２因子的连通３－正则图是上可嵌入的，即γＭ（Ｇ）＝ｎ４（ｎ为Ｇ的节点数ｎ＝｜Ｖ（Ｇ）｜）．然后，基于此证明了含四边形２因子且所有节点ｖ∈Ｖ的次ｄＧ（ｖ）＝３（ｍｏｄ４）的图Ｇ均为上可嵌入的     

带弦的圈是协调图

称具有ｅ条边的简单图Ｇ为协调图，若存在由Ｇ的顶点集到模ｅ的整数群Ｚｅ的一个单射ｈ，使得导出映射ｈ＾＊：ｈ＾＊（ｕｖ）≡ｈ（ｕ）＋ｈ（ｖ）（ｍｏｄ ｅ）是一个由Ｇ的边集到Ｚｅ的双射，带弦的圈Ｃ′ｎ是由含ｎ个顶点的圈Ｃｎ上添一条连结两个不相邻顶点的边而得到的图。本文中证明了，除了ｎ＝６且弦端点在Ｃｎ上的距离为２的情况外，所有带弦的圈都是协调图。     

关于无爪Hamilton图的一个泛圈性结果

一个图Ｇ是泛圈的，如果它含有长为３，４，…，ｎ（＝｜Ｖ（Ｇ）｜）的圈．本文探讨了一类无爪Ｈａｍｉｌｔｏｎ图的圈结构，主要结果为：设Ｇ＝（Ｖ，Ｅ）是ｎ阶无爪Ｈａｍｉｌｔｏｎ图．如果Ｇ中有节点ｘ使ｄ（ｘ）≧ｎ／２且Ｎ（ｘ）连通，则除少数几个例外，Ｇ是泛圈的．     

邻域并和[a,b]-因子

设ａ＜ｂ是整数,Ｇ＝（Ｖ（Ｇ）,Ｅ（Ｇ））是一个图．Ｇ的一个支撑子图Ｆ称为Ｇ的一个［ａ,ｂ］－因子,若对任意的υ∈ＥＶ（Ｇ）,有ａ≤ｄ_Ｆ（υ）≤ｂ．本文得到了下列结果：设１≤ａ≤ｂ是整数,Ｇ是一个阶为ｎ的图,最小度δ（Ｇ）≥ａ且＞（ａ＋ｂ）（２ａ＋２ｂ－３）如果对于Ｇ的任意两个不相邻的顶点ｕ,υ有Ｎ_Ｇ（ｕ）ＵＮ_Ｇ（υ）≥ａｎ,则Ｇ有一个［ａ,ｂ］－因子．     

Cayley图的边Hamilton性

设Ｘ是有限群Ｇ的一个生成集．Ｃａｙ（Ｘ：Ｇ）表示生成集为Ｘ的Ｇ上的Ｃａｒｌｅｙ图，其顶点集为Ｇ，其边集为所有无序对［ａ，ｂ］组成的集合，其中ａ，ｂ∈Ｇ，ａ－１ｂ∈Ｘ∪Ｘ－１（Ｘ－１＝｛ｘ－１｜ｘ∈Ｘ｝）．若图的每条边都在的Ｈａｍｉｌｔｏｎ圈上，则称图是边－Ｈａｍｉｌｔｏｎ图．本文证明了：当Ｇ为ｐ－群或Ｈａｍｉｌｔｏｎ群时，若Ｘ含有Ｇ的中心元，则Ｃａｙ（Ｘ：Ｇ）是边－Ｈａｍｉｌｔｏｎ图．     

Induced subgraphs with large degrees at end-vertices for hamiltonicity of claw-free graphs

A graph is called claw-free if it contains no induced subgraph isomorphic to K1,3. Matthews and Sumner proved that a 2-connected claw-free graph G is Hamiltonian if every vertex of it has degree at least (|V(G)|-2)/3. At the workshop C&C (Novy Smokovec, 1993), Broersma conjectured the degree condition of this result can be restricted only to end-vertices of induced copies of N (the graph obtained from a triangle by adding three disjoint pendant edges). Fujisawa and Yamashita showed that the degree condition of Matthews and Sumner can be restricted only to end-vertices of induced copies of Z₁ (the graph obtained from a triangle by adding one pendant edge). Our main result in this paper is a characterization of all graphs H such that a 2-connected claw-free graph G is Hamiltonian if each end-vertex of every induced copy of H in G has degree at least |V(G)|/3+1. This gives an affirmative solution of the conjecture of Broersma up to an additive constant.     

2-连通无爪图的连通因子

若图G不含有同构于K1,3的导出子图,则称G为一个无爪图.令a和b是两个整数满足2≤a≤b.本文证明了若G是一个含有[a,b]因子的2连通无爪图,则G有一个连通的[a,b 1]因子.     

Compact Compatible Topologies for Posets and Graphs

A topology on the vertex set of a comparability graph G is said to be compatible (respectively, weakly compatible) with G if each induced subgraph (respectively, each finite induced subgraph) is topologically connected if and only it it is graph-connected; a weakly compatible topology on the vertex set of a graph completely determines the graph structure. We consider here the problem of deciding whether or not a comparability graph has a compact compatible or weakly compatible topology and in the case of graphs with small cycles, hence in the case of trees, we give a characterization.     

关于k-消去二分图的一些结果

图 G的一个 k-正则支撑子图称为 G的 k-因子 ,若对 G的任一边 e,图 G- e总存在一个 k-因子 ,则称 G是 k-消去图 .证明了二分图 G=( X,Y) ,且 | X | =| Y|是 k-消去图的充分必要条件是 k| S|≤ r1 + 2 r2 +…+ k( rk+… + rΔ) - ε( S)对所有 S X成立 .并由此给出二分图是 k-消去图的充分度条件 .     

关于图是(r,n)-临界图的一个邻域条件

设n，m和r是满足r≥2，n≥0，m≥3的整数，且当r是奇数时，假设r≥m-1．称一个图为K1,m-free，如果它不包含以Kt,m为导出的子图．称一个图G为一个（r,n）-临界图，如果在删去G的任意n个点后，剩下G的子图都有一个r-因子,设G是一个Kl,m-free的（n＋1）-连通图，且阶为｜G｜以及r（｜G｜≥n）是偶数,证明了：如果G的最小度至少是r＋n＋m-1，阶｜G｜≥8r5＋n，并且对V（G）的任意独立点集{x1，x2}都有｜NG（x1）∪NG（x2）｜≥（｜G｜＋n）／2，那么G是一个（r,n）-临界图．关于G的最小度和｜NG（x1）∪NG（X2）｜的下界是紧的。     

Die chromatischen Polynome unterringfreier Graphen

Let G be a finite undirected graph without loops and multiple edges. A graph is called “unterringfrei”, if there is no induced subgraph being a cycle of length?4. This note shows that the chromatic polynomial of such a graph does only have positive integers as its roots. Conversely all polynomials with only positive integral roots are the chromatic polynomials of such graphs under the slight restriction that M(G;α)=0 implies that M(G;β)=0 for α>β?0.     

K3-free图的线图的哈密顿性

设G是一个简单图，Gi G，G1在G中的度定义为d（Gt）=∑v∈v（c）d（v），其中d（v）为v在G中的度数。本文的主要结果是：设G是n≥2阶几乎无桥的简单连通K3-free图，且G≌k1,n-1、Q1和Q2，若对G中任何同构于四个顶点路的导出子图I有d（I）≥n＋2，则G有一个D-闭迹，从而G的线图L（G）是哈密顿图。     

Chromatic Number of Graphs each Path of which is 3-colourable

In his paper “Fruit salad” (mixed for Paul Erdos) Gyárfás has posed the following conjecture: If each path of a graph spans at most 3-chromatic subgraph then the graph is k-colourable (with a constant k, perhaps with k = 4). We will show that these graphs are colourable with 3 · Illg_c ¦V(G)¦? colours for a suitable constant c = 8/7. As a corollary we obtain that every graph G admits a partition of its vertex set V(G) into at most Illg_c ¦V(G)¦? subsets V_i for a suitable constant c = 8/7, such that the components of each induced subgraph G[V_i] are spaned by a path.