关于几乎正则2-连通图的Hamilton性的注记

研究几乎正则图的Hamilton性,得到了定理1 设G是2连通的(k,k+1)图,并且k≥V(G)3+13,如果G是偶数阶的图,则G是Hamilton图.定理2 设G是(k,k+2)图,并且k≥n3+103,如果存在G的一个非空独立集B1,使得B1≥n3-133,而且对于G的所有独立集B,都有B≤n2-1,则G是Hamilton图.

几乎正则的n-部竞赛图的若干性质

设D是一个有向图 ,D中所有可能的两点x与y(x与y可以相同 )的出度与入度之差的绝对值的最大值叫做有向图D的非正则性 ,并记为i(D) .如果i(D) =0 ,则称D为正则图 ;如果i(D) =1 ,则称D为几乎正则图 .

正则二部竞赛图的竞争指数

设D是一个有向图,如果存在无向图G满足V(G)=V(D),且对G中任意的顶点x,y相邻当且仅当G中包含顶点z,使得存在从x到z以及从y到z的长为m的途径,则称G为D的m步竞争图,记为C^(m)(D).若存在最小正整数q,使得C^(q+i)(D)=C^(q+i+r)(D),其中r是某个正整数,i是所有非负整数,则称q为D的竞争指数,记为cindex(D).给出了几乎正则二部竞赛图的竞争指数等于1时的充要条件,并进一步刻画了k正则二部竞赛图的竞争指数等于1和2时的充要条件。

极大饱和图D(n,k)的极值性质及圈唯一性

本文证明了极大饱和图D(n,k)的一个极值性质:在与D(n,k)具有相同度序列的所有图中,唯有D(n,k)含有最少的K_3子图,并由此推出,在几乎正则图的范围内,k个完全图之并及完全k部多分图均是圈唯一的。本文还用图谱方法,证明了完全二分图K_(m,n)的圈唯一性。

几乎正则多部竞赛图中弧的外路

Guo(Discrete Appl.Math.95(1999)273-277)提出外路的概念.有向图中一个顶点x(或弧xy)的一条外路是指起始于x(或弧xy)的一条路使得x控制这条路的终点仅当终点也控制x.一条长为k的外路称为k-外路.本文证明了一个几乎正则c-部(c≥8)竞赛图D中,如果D的每个部集至少包含两个点,则D中每条弧有(k-1)-或k-外路,其中k∈{3,4,…,|V(D)|-1}.进一步,当D是一个几乎正则c-部(c≥8)竞赛图,且每个部集所含顶点数目相同时,D的每条弧在k-或(k+1)-圈中,其中k∈{3,4,…,|V(D)|-1}.