本文主要研究有向图中的泛路问题.阶为n的有向图D中,u,υ是泛路点对是指u,υ之间存在长为k的路,其中k=1,2,·…,n-1.阶为n的有向图D中的泛路是指D中存在长为k的路,满足k=1,2,…,n-1.本文分为四章,主要内容如下：第一章的第一部分介绍了有向图的一些基本概念和术语.第二部分给出了圈与路的一些重要结果.第二章的第一部分主要讨论了特殊竞赛图中的泛路点对,得到了以下结果：定理设T是n个顶点的非强竞赛图,其中d+（u）=max{d+（x）；x∈V（T）},u1,u2,…,un-1是T[V（T）＼{u}]的n-1个顶点标号,且T[V（T）＼{u}]是强竞赛子图.同时有d+（u1）≤d+（u2）≤…≤d+（un-1）,设u,υ∈V（T）满足下列条件（1）如果d+（u）=n-1,υ可任意.（2）如果d+（u）≤n-1,对于强竞赛子图T[V（T）＼{u}]的点υ,d+（υ）=min{d+（x）；x∈V（T）＼{u}且x不是桥首}则u,υ是泛路点对.定理设T是一个阶为n的竞赛图,整数k满足3<k≤n,且k≥2δ+（T）+2.如果T包含一个t-路Pt,这里t<k,并且若对某个u∈V（Pt）有N-（u）（?）V（Vt）,则在T中存在路只+1,只+2,…,Rk,使得|V（Pi）|=i和V（只-1）（?） V （Pi）,其中i有t+1≤i≤k.第二章的第二部分讨论了一般竞赛图中的泛路及泛路点对,得到了以下结果：定理每个竞赛图都是泛路的.定理设T是阶为n≥3的强竞赛图.其中V（T）中的任一对顶点u,υ之间存在长为k的路,整数k满足2≤k≤n-1.定理设T是阶为n≥3的一个非强竞赛图,在T中存在一对顶点u,υ,它们之间有长为k的路,其中整数k满足1≤k≤n-1.第三章讨论了半完全n-部有向图的一个注记,得到了以下结果：定理V1,V2,…,V。是一个半完全n-部有向图D的n个部集. V（D）的一个分划V（D）=Y1∪Y2∪…∪Yp,Yi∩Yj=φ,i≠j,且K（?）Yj,1≤i<j≤p,并且要么对某个j∈{1,2,…，n}有Yi=Vj,要么D[Yi]是含有至少两个顶点的一个强连通半完全有向子图,则存在一对顶点u,υ,使得u,υ之间有长为k的路,其中k满足1<k<n-1.定理设D是一个二重正则c-部竞赛图,其中c≥5,u,υ是D中的一对顶点,使得u,υ之间存在长为k的路,整数k满足2≤k≤c-1.第四章讨论了强内竞赛图中的泛路及泛路点对,得到了下面的结果：定理设D是阶为n≥5的一个强内竞赛图,满足则D中存在一对顶点u,υ,它们之间有长为k的路,k=4,5,…,n-1.定理强内竞赛图是泛路的.
本文来源: https://www.lw50.cn/article/deb6541dd3c058862c5756f6.html