一种用4-圈和8-圈对二分图的划分

证明了如果一个平衡二分图G包含4k个点,k≥2,并且对G中每一对满足x∈V₁,y∈V₂的不相邻顶点x和y成立d(x)+d(y)≥2k+1, 则G包含k-2个4-圈和一个8-圈,并且这k-1个圈点不相交。     

图中相互独立的4-圈和8-圈

设 G 是一个含有4k 个顶点的简单图,若δ（G）≥2k,则 G 包含 k －2个4-圈和1个8-圈,使得这 k －1个圈是相互独立的。在此基础上证明了：若 G 是一个含有4k（k≥4）个顶点的图,δ（G）≥2k,则下列两种情况中至少有一种成立：（1）G 包含 k －3个4-圈和1个12-圈;（2）G 包含 k －4个4-圈和2个8-圈。且不论哪一种情况成立,这k －2个圈点不交。     

图中包含4-圈和6-圈的[1,2]-因子

设k为一个正整数,图G是一个顶点数为4k的简单图,当δ(G)≥2k+1时,文章证明了图G包含一个由k-3个4-圈,一个6-圈及一条至少包含三条弦的6-路构成的[1,2]-因子.     

(s,k)-连通图

图G为（s,k）-连通图,如果G中任意s个顶点的导出子图是k-连通的。证明了：如果s-k≤｜G｜-1/2,则（s,k）-连通图G是完全圈可扩的。由此推出,若图G的连通度κ（G）≥｜G｜＋1/2,则G是完全圈可扩的。     

正则2-连通图的最长圈

P.Erdos和A M Hobbs在[1]中提出如下的结论:设k≥6,G是2k个顶点的(k-2)次正则的2-连通图,则G是Hamilton图(以下简称为H图)。本文提出比上述结论更为广泛的定理:定理1 设k≥4,G是n个顶点的(k-2)次正则的2-连通图,则除G是peterson图外,G必有个长至少为min{n,2k}的圈。由于:(i)定理1中的k=4时,G是2-正则2-连通图,G是H图,它有个长为n≥min{n,2k}的圈;(ii)定理1中的k≥5且n≤3(k-2)时,根据[2]中的B.Jackson定理知,这时G是H图,它有个长为n≥min{n,2k}的圈。因此,要证明定理1成立,只要证明如下的定理2成立。定理2 设n≥3k-5≥2k,G是n个顶点的(k-2)次正则的2-连通图,则除G是Peterson图外,G必有个长至少为2k的圈。在证明定理2的过程中,本文作下列的假设:     

两类积图的(2,1)-全标号

图G的一个k-(2,1)-全标号是一个映射f:V(G)∪E(G)→{0,1,…,k},使得任意2个相邻的点和相邻的边有不同值,且任一对相关联的点和边的值差的绝对值至少为2.G的(2,1)-全标号数λt2(G)定义为G有一个k-(2,1)-全标号的最小的k值.刻画了圈与圈、路与路笛卡尔积图的(2,1)-全标号数.     

k-连通[k+3,k]-图中的Hamilton路

如果G的任意s个点的导出子圈中至少含有t条边,则称图G为[s,t]-图.本文证明了若G是k-连通[k+3,k]-图(k≥2),则G或者含有Hamilton路或者同构于Kk+2∨ Gk(其中Gk是含有k个点的任意图).     

满足一定度条件的图中4-圈的个数

证明了如果一个图包含4k个点, 并且任意两个不相邻的点的度之和大于或等于4k-2, 则该图一定含有k-1个点不相交的4-圈。     

判断k-可序哈密顿-连通图的新条件

具有n个顶点的图G(n≥3)是k-可序哈密顿-连通的(k是整数,且2≤k≤n),如果对于G中每一个具有k个不同顶点的可序集合S={v1v2,…,vk},都存在G中的哈密顿路P包含S且不改变其中元素的次序.本文证明了:对于具有n个顶点的图G,u、v是G中任意两个不相邻的顶点,且d(u)+d(v)≥n+1.如果G是「k+1/2﹁-连通的k-可序图,k是整数且2≤k≤n/12,则G是k-可序哈密顿-连通图.     

韧度与分数(k,n′)-临界消去图

设G是一个图,若去掉G中的任意n′个顶点的剩余子图仍是分数k-消去图,则称G是一个分数(k,n′)-临界消去图.文章证明了当t(G)≥((k2-1)(n′+1))/k,且n>k+n′+1时,G是分数(k,n′)-临界消去图.     

Kn—e图中的路因子

G是一个Kn-e图,e∈E（Ka）。设σ2（G）表示不相邻顶点度和的最小值．令｜V（G）｜=n=∑^ki=1 a,并且σ2（G）≥,n＋k-1．证明对于图G中任意的k个顶点v1,v2,…vk。存在点不相交的路P1,P2,…Pk,使得对于1≤i≤k,都有｜V（Pi）｜=ai．并且vi是Pi的一个端点．     

图的λ4-最优性的邻域交条件

文章给出了图的λ4-最优性的邻域交条件.设图G是阶至少为34的λ4-连通图,若对G中任意一对不相邻顶点u,v,都有｜N（u）∩N（v）｜≥6且ξ4（G）≤3n（G）/2＋3,则G是λ4-最优的;若对于λ4-连通图G中任意一对不相邻顶点u,v,都有｜N（u）∩N（v）｜≥6且对图中每个三角形T至少存在一个顶点v∈V（T）...     

泛圈图的一个新的充分条件

设G是一个阶为n的2－连通简单图,αv表示G中包含点v的最大独立集的点数,对任意uv不属于E,设Tuv=V\(N(u)∪N（v)),αuv=min{αu,αv}。本文证明了：如果对于任一对不相邻点u,v,｜N（u)∩N(v)｜≥min{αuv-1,｜Tuv｜},则除了一些特殊图外,对于G的任一点x和任意整数k(4≤k≤n),G包含长度为k县包含点x的圈。     

关于正则二部图的Pebblinq数

图G的pebbling数f（G）是最小的正整数n,使得不管n个pebble如何放置在G的顶点上,总可以通过一系列的pebbling移动把一个pebble移到图G的任意一个顶点上,其中图G的一个pebbling移动是从一个顶点移走2个pebble,而把其中的一个移到与其相邻的一个顶点上。证明了具有2m个顶点的k-正则二部图的Pebbling数为2m,其中k≥[（m＋1）／2]。     

具有固定匹配数的极值k-部k-一致超图的结构

设V1,V2,…,Vk为k个有限集,i∈{1,2,…,k},ni△=|Vi|,n△=min{n1,n2,…,nk}.H为一个以V1,V2,…,Vk为顶点类的k-部k-一致超图,v(H)表示H的匹配数,|H|表示H的边数.设t为一个给定的整数.首先证明:如果v(H)≤t,则|H|≤tn1n2…nk/n.当v(H)=t,|H|=tn1n2…nk/n时,确定了H的结构.     

关于几乎k-可扩图的若干结论

设G是具有奇数个顶点的图,k是非负整数且满足V(G)≥2k+1,若G中任意一个k-匹配都可以扩充为G的一个几乎完美匹配,则称G是几乎k-可扩图.文中证明了连通的几乎1-可扩图与2-连通的几乎k-可扩二部图分别添加一个新边后仍保持原来的可扩性.     

对称群Sn（n≤15）的一个新刻画

本文首先通过计算给出了对称群Sn（n≤15）的阶｜Sn｜,最高阶元的阶k1（Sn）,次高阶元的阶k2（Sn）及第三高阶元的阶k3（Sn）。然后利用有限单群分类定理证明了Sn（n=1,2,…,9,11,13,14）可由｜Sn｜和k1（Sn）刻画,即有限群G同构于Sn当且仅当｜G｜=｜Sn｜且k1（G）=k1（Sn）。最后对Sn（n=10,12,15）证明了它们可由｜Sn｜和k1（Sn）,k2（Sn）及k3（Sn）刻画,即G 同构于Sn当且仅当｜G｜=｜Sn｜且k1（G）=k1（Sn）,k2（G）=k2（Sn）及k3（G）=k3（Sn）。     

有向二部图中的独立有向6-圈

证明了若有向二部图D=(V1,V2:A)的最小度至少为5k,则D有k个顶点不交的独立有向6-圈.其中 |V1|=|V2|=3k, k为整数.     

虚二次域Q(a2-4kn)类数的可除性

设D是无平方因子正整数，h(-D)是虚二次域Q(-D)的类数.当D=4kn-a2时，其中a,k,n是适合k＞1，n＞1的正整数，除了几种已知的情况以外，必有n/2｜h(-D)或n｜h(-D).     

单群A11的一个特征性质

设G是一群.πe（G）表示群G的元素阶的集合,mi：=｜{g∈G｜g的阶为i}｜表示群G中i阶元个数,nse（G）={mi｜i∈πe（G）}表示群G中同阶元的长度的集合.本文对单群A11给出了新的刻画,即证明了：GA11,当且仅当下面条件成立：（1）｜G｜=｜A11｜,（2）nse（G）=nse（A11）.