Cayley图的边Hamilton性

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

图的最大亏格与2-因子

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

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

设Ｇ是一个ｎ阶图,若对于每一个ｋ（３≤ｋ≤ｎ）,Ｇ都含有长度为ｋ的圈,则称Ｇ为泛圈图． 在［１］中, Ｒ．Ｊ, Ｆａｕｄｒｅｅ等证明了如下结果： 定理Ａ设Ｇ是一个ｎ－阶２－连通图,δ（Ｇ）≥ｔ．若对于Ｇ中任意两个不相邻的点ｕ和ｖ,均有 ｜Ｎ（ｕ） ∪ Ｎ（ｖ）｜≥ｎ－ｔ,则 Ｇ是 Ｈａｍｉｌｔｏｎｉａｎ图． 根据 Ｂｏｎｄｙ在［４］中的想法：几乎任何一个 Ｈａｍｉｌｔｏｎｉａｎ图的非平凡的充分条件都可能蕴含着图的泛圈性质,自然有如下猜测：设图Ｇ满足定理Ａ的条件,则Ｇ是泛圈圈或者 ｎ＝２ｔ; Ｇ≌Ｋ_（ｔ,ｔ）…     

图的字典序积和自同态幺半群

Ｆ．Ｈａｒａｒｙ￣［１］和Ｇ．Ｓａｂｉｄｕｓｓｉ￣［２］考虑过图Ｘ和ｙ的字典序积Ｘ［Ｙ］的自同构群ＡｕｔＸ［Ｙ］与它们各自的自同构群的圈积ＡｕｔＸ［ＡｕｔＹ］的关系，并给出了两者相等的一种刻划．在本文，我们考虑更广意义上的问题，即Ｘ［Ｙ］的自同态幺半群ＥｎｄＸ［Ｙ］与各自的自同态幺半群的圈积ＥｎｄＸ［ＥｎｄＹ］的关系，也给出了两者相等的一种刻划，同时得到了下面结果：如果Ｘ和Ｙ都是不含Ｋ＿３导出子图的连通图，且其中之一图有奇数围长，那么ＥｎｄＸ［Ｙ］＝ＥｎｄＸ［ＥｎｄＹ］．     

关于点的度在modulo下等值的上可嵌入图类

结合４－边形２－因子条件,确定了一类点的度在ｍｏｄｕｌｏ４下值为０,１的上可嵌入图类,从而综合已有的结果,较完整地刻划了这类图的上可嵌入性情况。     

图的导出森林2-划分

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

复合图的1－因子分解

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

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

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

△(G)=3的外平面图的邻强边染色

对图Ｇ（Ｖ,Ｅ）,一正常ｋ－边染色ｆ称为Ｇ（Ｖ,Ｅ）的一邻强边染色,当且仅当对任意ｕｖ∈Ｅ（Ｇ）有ｆ［ｕ］≠ｆ［ｖ］．其中ｆ［ｕ］＝｛ｆ（ｕｗ）｜ｕｗ∈Ｅ（Ｇ）｝,ｆ（ｕｗ）表示染边ｕｗ的色,并称ｘａｓ（Ｇ）＝ｍｉｎ｛ｋ｜存在Ｃ的一ｋ种色的郁强边染色｝为Ｇ的邻强边色数．本文证明了对△（Ｇ）＝３的２－连通外平面图,有ｘａｓ（Ｇ）＝４．     

点可迁图的限制边连通度

设Ｓ是连通图Ｇ的边子集．如果Ｇ－Ｓ不连通而且不含孤立点，那么称Ｓ是Ｇ的一个限制边割，Ｇ中所有限制边割中最小边数称为Ｇ的限制边连通度，记为λ＇（Ｇ）．限制边连通度是对传统边连通度的推广，而且是计算机互连网络容错性的一个重要度量．点可迁图是一类重要的网络模型．本文证明了如下结论： 设 Ｇ是连通的点可迁图．如果 Ｇ的点数ｎ≥ ４，而且点度ｋ≥ ２，那么或者λ＇（Ｇ）＝ ２ｋ－２，或者ｎ是偶数，Ｇ含三角形且存在整数ｍ≥２，使得ｋ≥λ＇（Ｇ）＝ｎ／ｍ≤２ｋ－３．关