一类竞赛图的弧泛回路

设竞赛图T=(V,A),V为顶点集合,A为弧集合。如果T中每一条弧e,都存在一个长度为3的回路经过e,则称T具有弧三回路性质。如果T中每一条弧e,都存在|T|-2条长度分别为3,4,…,|T|的回路经过e,则称T具有弧泛回路性质。如果T中每一个顶点的出入度都相等,则称T为正则的。 Alspach在他的博士论文中证明了正则竞赛图具有弧泛回路的性质。本文将指出有     

3-超竞赛图的控制图

控制图被建立在一个竞赛模型中,用以反映个人或者团队在竞赛中的竞争关系。设T是一个k-超竞赛图并且x和y是T的两个顶点,如果对于T中所有与x和y不相同的顶点z,有|A_T(x; z)|≥|A_T(z; x)|或者|A_T(y; z)|≥|A_T(z; y)|,那么点x和y控制k-超竞赛图T.用dom (T)表示k-超竞赛图T的控制图,其中顶点集为k-超竞赛图T的顶点集,如果dom(T)的两个顶点控制T,那么这两个顶点在dom(T)中相邻。1998年,FISHER D刻画了竞赛图的控制图的结构。文章将竞赛图的控制图推广到超竞赛图中,进一步确定了一个点数为n≥4的3-超竞赛图的族T并且证明了以下结果。(1)设T=(V(T), A(T))是一个点数为n≥4的3-超竞赛图并且n是奇数,那么C_n是dom(T)的一个子图当且仅当T∈J.(2)设T=(V(T),A(T))是一个点数为7的3-超竞赛图。那么NC7不是dom(T)的一个子图。     

竞赛图是K-圈图的充分条件

在[1] 、[2] 和[3] 里,研究了一个定向图是“泛圈”(pancyclic)的条件。最近朱永津等同志,讨论了一个竞赛图是强路联通的条件。本文将讨论一个竞赛图是 k-圈图的条件。一个定向图是称为 k-圈图,如果它的任何 k 个顶点{x_1,x_2,……,x_k},就有一个长度为 k 的简单回路,而这条回路恰由这 k 个顶点组成。一个无环的定向图,若它的任意两个顶点之间有一条且仅有一条孤,则称它为竞赛图,我们用 T(X,A)来表示它。     

竞赛图中的回路与道路

末文讨论竞赛图中的回路与道路问题,给出了图中的最小度与回路以及道路之间关系的若干结果,证明了: 定理1 若T是竞赛图,,δ~ (T)≥k≥1(或δ~-(T≥k≥1),则T中含有长度≥2k 1的回路。定理2 若P≥3阶竞赛图T满足δ(T)≥h≥1,δ(T)≥j≥1,且h j≥(P-1)/2,则中存在Hamilton回路。定理3 若竞赛图T满足δ(T)≥h,δ~-(T)≥k,且min{h,k}≥2,则T中任何弧或者会在一条Hamilton道路上,或者会在某条长至少为k h 2的道路上。     

唯一有向Euler图的构造

<正> 如果一个有向Euler图的有向Euler环游是唯一的,我们就称之为唯一有向Euler图。本文直接由文 [1] 给出的唯一有向Euler图的充要条件,来证明关于唯一有向Euler图的构造定理,即定理设D是有向Eulcr图,则当且仅当D是由若干个有向回路在入度和出度都是1的顶点上逐个粘接而成时,D是唯一有向Euler图。     

组合竞赛图的控制图

竞赛图是完全无向图的定向图,具有任意两个顶点之间有且仅有一条弧的性质。竞赛图的控制图和竞争图有比较紧密的联系,对竞赛图的控制图的研究由来已久,并在生物竞争图的结构刻画上起到了重要的作用。设T是c个顶点的竞赛图,S_i(i=1,2,…),c分别是竞赛图,那么称D=T[S_1,S_2,…,S_c]为T的组合竞赛图。通过研究组合竞赛图的控制图的性质和结构,对原有针对竞赛图的定理进行扩充,针对如何求解竞赛图的控制图,推导并求解组合竞赛图的控制图,并给出相应算法。     

具有弧泛回路性竞赛图顶点的非正则性

1967年B.Alspach开始研究竞赛图的弧泛回路性,在[1]中证明了:正则竞赛图必具有弧泛回路性。又吴正声等在[2]中研究了具有弧3—回路竞赛圈顶点的非正则性,得到了某些结果。由此,考虑具有弧泛回路性竞赛图顶点的非正则性,能否得到[2]中相应的结果,这是一个值得研究的问题。作者在吴正声老师的具体指导下,对这一问题进行了初步探讨,得到了与[2]完全类似的结果。     

关于竞赛图的一些结果

§1 有序定向竞赛图中的哈密尔顿回路令U_1,…,U为竞赛图T中的顶点。令d_(?)~ 为U_i的出度。如果每个U_i恰好指向U_(i 1),…,U_(i d~ ),(modn),其余的顶点指向U_i,则T被称为有序定向的。 Alspach等人曾在这类图中的回路计数问题上作了一些工作。本文将讨论的是这类图中哈密尔顿回路的计数问题。Thomassen曾提出这个问题:在同样的出度序列条件下,那一     

竞赛图的零因子半群

讨论了竞赛图的零因子半群.一个半群S的零因子图是一个有向图Γ(S),其顶点是S中非零的零因子,S中两个不同的元x,y有一条有向边x→y当且仅当xy=0.该文证明了如果S是一个没有非零幂零元的有限半群且图Γ(S)的顶点数大于1,那么图Γ(S)不是一个竞赛图.另外对于任意的正整数n,该文完全决定了顶点数为n蹬任一个竞赛图的所有零因子半群.     

竞赛图中的完美对集

Lichiardopol在离散数学-竞赛图中经过给定的0,1,2个公共顶点的圈一文中提出以下两个公开问题;对于阶为2n+1的正则竞赛图T,(a)对任意的一个顶点w,是否存在n个有向三角形Ti生成T,且使得V(Ti)∩V(Tj)=w(1≤i相似文献   

竞赛图的定序哈密尔顿回路

竞赛图T(V,A),V_1为V的任意一个子集,V_1={v_1,…,v_1}。若有一个回路C={u_1,…,u_r,u_t}经过V_1的诸点,即v_1=u_1,(i=1,2,…,t),并且,i,相似文献   

有向路的重构

在Harary和Palmer的有关有向图的重构的基础上得到:若有向路的顶点数大于4,则可以利用它的一组有向子树重构该有向路.结合Harary和Palmer给出的有向图的重构定理,推出结论:设T是有ν(ν≥4)个顶点的有向树,则T可由其子图{T-vi}完全确定(其中i=1,2,…,ν).     

优美树问题简介

§1.引言设N_n={1,2,…,n},T是有n-1条边的树(n≥2)。所谓T的一个优美值θ是指由T的顶点集V到N_n的一个双射(即由V到N_n的一个一一映射),使l(uv)=|θ(u)-θ(v)|是T的边集E到N_(n-1)的一个双射,这里uv表示联结顶点u和v的边。若树T有一个优美值,则说树T是优美的(参看图1)。在一般情况下,当T是一个有n-1条边的简单图,θ是由V到N_n的一个子集的双射,且l(u,v)满足上述条件,则这图就叫优美图(参看图2)。     

二部图匹配的一个判别条件

根据Hall定理,二部图G=(V1,V2;E)有一个浸润V1匹配的充要条件是:SV1,N(S)∩V2≥S,即V2中与V1的任一子集S相邻的顶点数不小于S中的顶点数。当V1中的顶点数较多时,用该条件判定较为困难。本文给出了一个基于顶点度判别二部图有浸润匹配的条件,并应用该条件解决了一个关于图的二划分的问题。     

一类竞赛图顶点的非正则性

B.Alspach在[1]中,证明了正则竞赛图的弧泛回路性,并举出了偶数个顶点的几乎正则图不含3—回路的反例。朱永津、田丰在[2]中,提出了竞赛图的O(p,q)条件,并证明了具有O(p,2)条件的竞赛图的任意弧总存在过这弧的任意长的回路系列(除3—-回路外)。又刘振宏、蔡茂诚在[3]中,证明了q=1等价于竞赛图的正则性,并得出了图的最     

正则竞赛图的有向生成三角形

2008年N.Lichiardopol在离散数学-竞赛图中经过给定0,1,2个公共顶点的圈.一文中提出以下公开问题:阶为2n+1的正则竞赛图T,对于任意的x∈V(T)是否存在n个有向三角形Ti使得V(Ti)∩V(Tj)=x(1≤i≤j≤n).文章证明了对于阶数为5,7,9的正则竞赛图,该问题答案是肯定的.     

立方图的可圈性

图的可圈性是哈密尔顿性的一个推广.设G是有向图,如果对G的每一个定向D,都存在S(D) V(G)使在D中改变所有恰与S(D)中一个顶点相关联的弧的方向后所得到的图为有向哈密尔顿图,则称G为可圈图.证明至少含5个顶点的连通图G的立方图是可圈图当且仅当G不同构于任何一条偶路.该结果改进了Klostermeyer的3个定理.     

竞赛图具弧泛旁路性的最优估界

记■,本文证明了当竞赛图T的顶点p≥5k 4,i(T)≤k,k≥4时,竞赛图具弧泛旁路性。     

图有较高连通度的一个充要条件

图的连通性理论是图论学科重要而基础的研究领域,通过该领域的研究,人们对图的结构和性质有了进一步的认识,并且将所得到的结果应用于网络设计、城市交通等实际问题中,取得了很多应用成果,例如,量化一个图或网络的脆弱程度,便始于图的连通性研究。因此,我们总是希望图能具有较高的连通度。对n个顶点的图G来说,当连通度不小于顶点数n的一半时,我们认为这个图有较高的连通度。本文试图给出图具有较高连通度的一个充分必要条件。我们指出,对一个给定的正整数k且k≤2n,有κ(G)≥n-k成立当且仅当对顶点集V(G)的任意一对不交子集S和T,G[S,T]有一个完美匹配,这里|S|=|T|=k,G[S,T]=G[S∪T]-E(G[S])-E(G[T])。     

Tss图的弧k-回路性

若T是p个顶点的竞赛图,且它的平方图T~2是完全对称的,则称T为Tss(p)图,或简称为Tss图。