完全偶图的补图的特征根分布

设Ｇ为ｐ 阶连通简单图,其补图Ｇ为完全偶图Ｋｎ,ｍ 及空图Ｋ的并,笔者利用完全偶图的谱的特性,获得了图Ｇ的特征根分布     

图的第二个最小特征值的界

设Ｇ是ｎ个顶点的简单图，λｎ－１（Ｇ）为Ｇ的第二个最小特征值。Ｇ的非孤立点形成的图记为Ｇ１，Ｖ（Ｇ１）＝ｓ，（３≤ｓ≤ｎ）。本文主要证明了：ａ．若Ｇ１不是完全偶图，则λｎ－１（Ｇ）≤λｓ－１（Ｋ２，ｓ－２＾－ｅ），等式成立＝Ｇ１≌Ｋ２，ｓ－２＾－＾ｅ。其中图Ｋ２，ｓ－２＾－＾ｅ为完全偶图Ｋ２，ｓ－２去掉一边ｅ而得到的图ｂ．若Ｇ１既不是完全偶图，又不是Ｋ２，ｓ－２＾－ｅ，则λｎ－１（Ｇ）＜－√２／２     

关于CockayneEJ的两个猜想

猜想１〔１〕当Ｋ（Ｇ）＝Ｃ２ｎ＋１时有Ｃ（Ｇ）≤ｄ（Ｇ）;猜想２〔１〕当Ｋ（Ｇ）是偶图时有Ｃ（Ｇ）≤ｄ（Ｇ）．以下通过反例说明猜想１不成立．然后证明猜想２成立．设Ｇ是无向、无环、无多重边的简单图,Ｇ＝（Ｖ,Ｅ）,其中Ｖ＝Ｖ（Ｇ）表示Ｇ的顶点集,Ｅｎ＝...     

导出匹配可扩偶图的度条件

称简单图Ｇ为导出匹配可扩图，若Ｇ的任一导出匹配均含于Ｇ的完美匹配中。本文给出了导出匹配的可扩偶图的一些度条件。     

关于完全图的G—覆盖数的一些结果

给定无孤立点的简单图Ｇ,完全图Ｋ的Ｇ－覆盖定义为一个序偶（Ｖ,Ｆ）,其中Ｖ为Ｋ_ｖ的顶点集,Ｆ为Ｋ_v的一族子图,使得Ｆ中每一个子图都与Ｇ同构且Ｋ_v的每一条边至少出现在Ｆ的一个子图之中．完全图Ｋ_v的Ｇ－覆盖中所含的最少的子图个数称为它的Ｇ－覆盖数,记作（ν,Ｃ）．本文对五个顶点,五条边的４个图Ｇ,完全确定了Ｃ（ν,Ｇ）值．     

2和3连通图中的禁止子图与哈密顿性质

证明了如下结果：（１）若Ｇ是２－连通的（Ｋ１，３，Ｐ５，Ｂ）－自由图，或２－连通的（Ｋ１，３，Ｚ２，Ｐ５）－自由图，则Ｇ是哈密顿图，（２）若Ｇ是３－连通的（Ｋ１，３，Ｚ１）－自由图，或３－连通的（Ｋ１，３，Ｚ２，Ｐ５）自由图，或３－连通的（Ｋ１，３，Ｐ５，Ｂ）－自由图，则Ｇ是哈密顿连通的。     

图的升分解问题的两个新结果

Ａｌａｖｉ等人在１９８７年定义了图的一种新分解,即“升分解”（ＡｓｃｅｎｄｉｎｇＳｕｂｇｒａｐｈＤｅｃｏｍｐｏｓｉｔｉｏｎ）,并且猜想：任意有正数条边的图都可升分解．该文证明了下面两个新结果：（１）Ｈｉ是ｉ条边的Ｋｎ的子图,当ｎ＋１≤ｉ≤２ｎ－２ｎ／３［］２－２时,Ｇ＝Ｋｎ－Ｈｉ可升分解为Ｋ１,１,Ｋ１,２,…,Ｋ１,ｎ－５,Ｋ１,ｎ－４,Ｇｎ－３（ｎ≥６）,其中Ｋ１,ｎ－４Ｇｎ－３．（２）Ｈｉ是ｉ条边的Ｋｎ的子图,当ｉ≥２ｎ－２ｎ／３［］２时,Ｇ＝Ｋｎ－Ｈｉ不一定有定理１形式的升分解．     

不含K3图的周长

设Ｇ为不含Ｋ３的２连通的非偶图的图。Ｄ（ｕ）｛ｖ｜ｖ∈Ｖ（Ｇ），ｄ（ｕ，ｖ）＝２｝，δ０＝ｍｉｎ｛ｍａｘ（ｄ（ｕ），ｄ（ｖ）｜ｕ，ｖ∈Ｖ（Ｇ）且ｄ（ｕ，ｖ）＝２｝，Ｄ（δ０）＝｛ｕ｜ｕ∈Ｖ（Ｇ）且ｄ（ｕ）≥δ０｝，δ≥δ０时还满；     

关于二部图的圈的几个结果

高图Ｇ－（Ｘ，Ｙ；Ｅ）是二部图，ｈ＝ｍｉｎ（／Ｘ／，／Ｙ／）且ｈ≥３，δ（Ｇ）≥２，则（１）图Ｇ的周长Ｃ（Ｇ）≥ｍｉｎ（２ＮＣ２，２Ｈ），（２）若Ｇ是连通的，／Ｘ／＝／Ｙ／＝ｎ≥，且ＮＣ２＝ｎ，则Ｇ是偶圈可扩张的图且是偶泛圈图。     

K1,n—free图的f—因子

图Ｇ称为Ｋ１,ｎ－ｆｒｅｅ,若图Ｇ不包含同构于Ｋ１,ｎ的导出子图。设ｆ（ｘ）是定义在Ｖ（Ｇ）上的非负整数函数,Ｇ的一个支撑子图Ｆ称为Ｇ的一个ｆ－因子,若对任意的ｖ∈Ｖ（Ｇ）有ｄＦ（ｖ）＝ｆ（ｖ）,对Ｋ１,ｎ－ｆｒｅｅ图存在ｆ－因子涉及到最小度条件进行了研究,得到了一个充分条件。有关定理为本定理的特例。     

关于Faudree－Schelp定理的改进

一个图Ｃ＝（Ｖ，Ｅ）是［ｌ，ｍ］－泛连通的，如果在Ｇ的任意一对节点ｘ与ｙ之间有长为Ｋ—１的路Ｐｋ（ｘ，ｙ），Ｋ＝ｌ，ｌ＋ｌ，…，ｍ。Ｇ具有性质Ｐ（Ｋ），如果对Ｇ的任何一对距离为２的节点ｘ和ｙ，有ｄ（ｘ）＋ｄ（ｙ）≥Ｋ。作者探讨了一类产（Ｋ）图的路连通性，改进了Ｆａｕｄｒｅｅ－Ｓｃｈｅｌｐ定理，得到两个定理：定理１设Ｇ＝（Ｖ，Ｅ）是ｎ阶Ｐ（ｎ—１）图。如果Ｇ是［ｎ—１，ｎ］－泛连通的，则Ｇ是［８，ｎ］－泛连通图（ｎ≥８）．定理２设Ｇ是３－连通ｎ阶Ｐ（ｎ）图。如果Ｇ的独立数α（Ｇ）＜ｎ／２，则Ｇ是［５，ｎ］－泛连通图，ｎ≥５．     

张量积图的边联结数

本文研究了张量积图的边职结数，由于确定任意图的束积的边职结数很难，故限于讨论下列类型图的张量积：路（Ｌｎ），图（Ｃｎ）。完全图（Ｋｎ）和完全偶困（Ｋ＿（ｍ．ｎ）），已求得路与圈、圈与圈、路与完全图、圈与完全图、路与完全偶图、圈与完全偶图、完全图与完全图、完全图与完全偶图、完全偶图与完全偶图的张亡积图的边联结数。     

关于完全三部图K(n-k,n,n+k)的色性

设Ｇ为简单图,Ｐ（Ｇ,λ）的色多项式,若对任意简单图Ｈ满足Ｐ（Ｈ,λ）＝Ｐ（Ｇ,λ）,都有Ｈ与Ｇ同构,则称Ｇ是色唯一图,设Ｋ（ｍ,ｎ,ｒ）表示完全三部图,证明了：（１）对任意非负整数ｋ,若ｎ≥２√－３ｋ／３＋ｋ＾２,则Ｋ（ｎ－ｋ,ｎ,ｎ＋ｋ）是色唯一图。（２）若ｎ≥９,则Ｋ（ｎ－３,ｎ,ｎ＋３）是色唯一图。     

关于唯一r－偶泛圈图

设ｒ是不小于４的偶数，一个阶为ｖ（ｖ为偶数）的偶图Ｇ称为唯一ｒ－偶泛圈图，如果对每一偶数ｔ（ｒ≤ｔ≤ｖ），Ｇ恰含一ｔ圈，而不含长小于ｒ的圈。若Ｇ是唯一ｒ－偶泛圈图，则称Ｇ为ｒ－ＵＢ图，设Ｇ是ｒ－ＵＢ图，Ｃ是Ｇ的Ｈａｍｉｌｔｏｎ圈，本文约定Ｇ中不在圈Ｃ上的边全画在Ｃ的内部，并称这些边为Ｇ的桥．如果Ｇ的一条桥的两个端点在圈Ｃ上分离另一条桥的两个端点，则称这两条桥是交叉的．有ｎ对交叉桥的ｒ－ＵＢ图称为ｒ－ＵＢ［ｎ］图．本文确定了所有ｒ－ＵＢ［１］图．     

完全三部图K（n,n,n＋k）的色性

设Ｇ为简单图,Ｐ（Ｇ,λ）为Ｇ的色多项式。若对任意简单图Ｈ满足Ｐ（Ｈ,λ）＝Ｐ（Ｇ,λ）,都有Ｈ与Ｇ同构,则称Ｇ是色唯一图,设Ｋ（ｍ,ｎ,ｒ）表示完全三部图。证明了（１）对任意非负整数ｋ,若ｎ≥ｋ＋ｋ＾２／３,则Ｋ（ｎ,ｎ,ｎ＋ｋ）是色唯;（２）若ｎ≥４,则Ｋ（ｎ,ｎ,ｎ＋４）是色唯一图。     

最大外可平面图的树图

通过对最大外可平面图和Ｋ临界图的研究给出三个主要结论（１）最大外可平面图的生成树有２＾ｐ－３＊３棵。（２）最大外可平面图的树图ＧＴ,β（ＴＧ）≥ｐ＋１。（３）临界图Ｇ,当Ｋ（Ｇ）＝１时,树图ＧＴ是平凡图,当Ｋ（Ｇ）＝２时,对图ＧＴ是ｐ图。     

独立亲同调子图

设Ｋ是一个复形，Ｌ是Ｋ的一个子复形。如果所有从Ｌ的同调群到Ｋ的同调群的包含同态ｉ：Ｈｑ（Ｌ，Ｊ）→Ｈｑ（Ｋ，Ｊ）（ｑ≥０，Ｊ是整数解）都是同构，则称复形Ｋ同它的子复形Ｌ亲同调。对一个图Ｇ及其去边子图Ｆ，如果Ｆ的独立集复形Ｉ与Ｇ的独立集复形Ｉ（Ｇ）亲同调，则称图Ｇ与其子图Ｆ独立亲同调。     

关于Catlin的2／3—猜想

表示一个图，若Ｇ有一个欧拉生成图，则称Ｇ是超欧拉图。Ｃａｔｌｉｎ的２／３－猜想：设Ｇ是超欧拉图，Ｇ≠Ｋ１，则Ｇ存在一个欧拉生成子图Ｈ，使得Ｅ（Ｈ）／Ｅ（Ｇ）≥２／３。笔者证明了对于Ｃａｙｌｅｙ图，猜想成立。     

图Kn—E（kPs∪rK3）的色唯一性

利用不可约路的概念，证明了当Ｐｓ是不可约的路时，Ｋｎ－Ｅ（ｋＰｓ∪ｒＫ３）是色唯一的图，其中设Ｋｎ－Ｅ（Ｇ）表示从完全图Ｋｎ中删去一个和Ｇ同构的子图的所有边而得到的图，ｓ≠４，且ｋｓ＋３ｒ＝ｎ，ｋ３是有３个顶点的完全图，同时给出了三类新的色等价图簇。     

Super-Euler迭线图的特征刻划

图中端点度数不是２而内点的度数是２的路叫做枝。文中证明了一个连通图Ｇ的ｎ次迭线图Ｌ＾ｎ（Ｇ）是Ｓｕｐｅｒ－Ｅｕｌｅｒ图的充要条件是Ｇ有一个包含Ｇ的每个度至少为３的项点的子图Ｈ,满足：Ｈ的每个顶点都是偶度;Ｈ的孤立顶点在Ｇ中度至少为３;Ｈ的任何连通分支与Ｈ的其它连通分支在Ｇ中的距离至多是ｎ;对于Ｇ中不在Ｈ中的枝的长度至多为ｎ＋１,对于Ｇ中有端点度为１的枝的长度至多为ｎ。