关于竞赛图弧泛回路性的一类反例

设T(V,A)是p个顶点的竞赛图,若对于任意(v_0,v_1)∈A,在T中存在含有(v_0,v_1)的k-回路C_k(k=3,4,…,p),则竞赛图T称为具有弧泛回路性。若对于任意(v_0,v_1)∈A,在T中存在含有(v_0,v_1)的k-回路C_k(k=3,4,…,p—1),并且至少存在T的一条弧不含于T的任一p-回路中,则竞赛图T称为具有准弧泛回路性。 为了叙述方便引进下列记号: R(p)——p个顶点的正则竞赛图所组成的集合;     

竞赛图具有弧泛回路性的一个充要条件

本文的主要结果为:p个顶点的竞赛图T,具有弧泛回路性的充分必要条件是T具有弧3-回路与弧p-回路性。     

竞赛图具有弧泛回路性的一个充分条件

关于竞赛图的弧泛迴路性问题,Alspach证明了正则竞赛图具有此性质.朱永津、田丰证明了若竞赛图 T 中任意一个弧(v,v_0)都满足条件 d~+(v_0)+d~-(v)≥p-2,这里 p 为 T 的顶点数,则当 p≥7时,T 中过任一弧存在迴路系列 C_4,C_5,…,C_p.本文提出并证明了若 T 满足以下条件:当 d~+(v)<1/2(p-1)时,在 v 的外邻集 O(v)中有一点 u,d~+(u)≥1/2(p-1);当 d~+(v_1),d~+(v_2)<1/2(p-1)时,有 u_1,u_2∈O(v_1)∪O(v_2),d~+(u_1),d~+(u_2)≥1/2(p-1),且对入次亦满足相应的条件,则当 p≥9和最小次数δ≥4时,过 T 的每一个弧存在迴路系列 c_6,c_7,…,c_p.此充分条件不要求顶点次数的正则性和几乎正则性,对 T 的不正则度 q=(?)|d~+(v)-d~-(v)|一般来说也没有限制.     

关于竞赛图弧Hamilton回路性

邵品琮,张存铨提出如下猜想: 竞赛图T是弧Hamilton回路的。则T中每条弧l,都有一系列长为h,…,p的回路经过l(4≤h≤p—1)。 本文构造了一类图,它们具有弧Hamilton回路性,但不具有弧5回路性。并且证明若p≥7,则具有弧Hamilton回路性的p阶竞赛图T具有弧p-1回路性。     

一类泛圈图

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

一类泛圈图

本证明了如果G是2连通无爪图,G不是圈,n=|V(G)1≥9,G的每个导出子圈A都满足φ（a1,a2),且G中不含同构于Z^ 2的导出子图,则G是泛圈图。     

k-强竞赛图中外弧泛5顶点的数目

称具有n≥3个顶点的强竞赛图T中的一条弧是泛k的,如果对所有的k≤l≤n来说,它属于每个l-圈.本文证明了每个s-强(s≥4)竞赛图至少包含s+2个顶点使得它们的所有外弧都是泛5的.     

κ-强竞赛图中外弧泛5顶点的数目

称具有n≥3个顶点的强竞赛图T中的一条弧是泛κ的,如果对所有的κ≤l≤n来说,它属于每个l-圈.本文证明了每个s-强(s≥4)竞赛图至少包含s+2个顶点使得它们的所有外弧都是泛5的.     

一类新的泛圈图

本文所说的图都是简单无向图。未定义的术语和记号参见[2]。设 G=(V,E)的 n 阶图(n≥3),若 G 中含有 Hamilton 圈,则称 G 是 H-图。若G 中含有从3到 n 的所有长度的圈,则称 G 为泛圈图。如下两个定理是众所周知的。定理1 (Ore,1960)。若在 n 阶图 G 中,有uv(?)E(G)(?)d(u) d(v)≥n,则 G 是 H-图。     

竞赛图弧色数的上界

有向图的弧色数指的是对有向图的弧进行着色, 使得所有连贯弧着不同颜色所需要的最少颜色数. 在介绍了一些相关结果的基础上, 通过确定顶点数较少的竞赛图弧色数的最大值, 说明了已有弧色数的上界虽然对一般有向图是紧的, 对竞赛图却是可以改进的.     

弧哈密顿竞赛图的一个性质

§1.引言 设T是有p个点的一个竞赛图,T称为是弧k回路的,若T的每一条弧在一个长度为k的回路上.T也称为是弧哈密顿的,若T是弧p回路的.在第二次全国图论学术交流会上,邵品琮和张存铨提出下列猜想:     

一类几乎唯一泛圈图

设G是阶为n的简单Hamilton图．若存在m(3(?)m相似文献   

一类泛连通无爪图

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

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

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}.     

多部竞赛图中包含某条弧的圈

多部竞赛图或n部竞赛图是指一个完全n部无向图的定向图.2007年Volkmann证明了每个强连通的n部竞赛图(n≥3)至少存在一条弧它包含在从3到n的每个长度的圈中.在此基础上给出了强连通n部竞赛图中存在一条弧它包含在从3到n+1的每个长度的圈中的一个充分条件,并举例说明该条件在某种意义上的最佳可能性.     

二部竞赛图中的AD路与AD回路

本文证明了：若对二部竞赛图Ｔ的每一顶点ｖ，总有ｍｉｎ｛ｄＴ＾＋（ｖ），ｄＴ＾－（ｖ）｝≥ｋ≥３，则Ｔ中存在长度至少为４ｒ的ＡＤ路或ＡＤ回路，除非Ｔ同构于一类例外图之一。作为推论，我们得到：正则二部竞赛图Ｔ含有ＡＤＨ回路，除非Ｔ属于一类例外图。     

几乎正则多部竞赛图的点泛圈性

令T是多部竞赛图,i(T)=x,()|d+(x)-d-(y)|(这里允许x=y)如果i(T)=0,则T被称为是正则的;如果i(T)≤1,则T被称为是几乎正则的.Volkmann猜测几乎正则c-部竞赛图(c≥4)是泛圈的.本文证明当c≥5时,除了有限多个几乎正则多部竞赛图外,所有几乎正则c-部竞赛图都是点泛圈的.同时我们给出一个反例说明当c=4时,上述猜想不成立.     

几乎正则多部竞赛图的点泛圈性

令T是多部竞赛图;i（T）=|d+（x）-d-（y）|（这里允许x=y）,如果i（T）=0,则T被称为是正则的;如果i（T）≤1,则T被称为是几乎正则的.Volkmann猜测几乎正则c-部竞赛图（c≥4）是泛圈的.本文证明当c≥5时,除了有限多个几乎正则多部竞赛图外,所有几乎正则c-部竞赛图都是点泛圈的.同时我们给出一个反例说明当c=4时,上述猜想不成立.     

二部竞赛图中含指定点对的互补回路

设R是任一个k-正则二部竞赛图(k≥2),对R中任意两个不同的点u,v,R中存在一对点不相交且分别具有长4和4K-4的回路C_1、C_2,使得u在C_1上,v在C_2上,除非R同构于R_(494)~*。     

正则多部竞赛图中任意弧的所有长度的外路

多部竞赛图D中弧x_1x_2的一条(l-1)一外路是指起始于x_1x_2的长为l-1的路x_1x_2…x_1,其中要么x_1与x_1同部,要么x_1控制x_1.特别地,当l=|V(D)|且x_1控制x_1时,x_1x_2…x_lx_1是一个通过弧x_1x_2的Hamilton.Guo(Discrete Appl.Math.95(1999)273-277)证明了一个正则c-部(c≥3)竞赛图中的每条弧都有一个(k-1)-外路,其中k∈{3,4,…,c}.作为一个推广,该文证明了一个正则c-部(c≥5)竞赛图中的每条弧都有一个(k-1)-外路,其中k∈{3,4,…,|V(D)|}.进一步,使用路收缩技巧,下面一个结果也被证明:D是一个正则c-部(c≥8)竞赛图,且每个部集包含两个顶点,则D的每条弧被包含在一个Hamilton圈中.这个结果部分地支持了Volkmann和Yeo(Discrete Math.281(2004)267-276)提出的猜想:正则多部竞赛图的每条孤都包含在一个Hamilton圈中.