4-强连通竞赛图中外弧泛圈点的研究.pdfVIP

第29卷 第1期 太 原 科 技 大 学 学 报 Vo1．29 Nol 2008年2月 JOURNAL OF TAIYUAN UNIVERSITY OF SCIENCE AND TECHNOLOGY Feb．2008 文章编号：1673-2057(2008)01—0043—03 4一强连通竞赛图中外弧泛圈点的研究 张新鸿 ，李瑞娟 (1．太原科技大学应用数学系，太原030024；2．山西大学数学科学学院，太原030006) 摘 要：外孤泛圈点问题是图论研究中一个比较热门的问题，文章在某些限制条件下研究了4·强连通竞赛图的外 孤泛圈点问题。文中使用路收缩等方法证明并给出了4-强连通竞赛图中存在3个外孤泛圈点的一个充分条件，而且给 出了一些相关的结论。 关键词：4-强连通竞赛图；外孤泛圈点；外度；内度；路收缩 ～ 中图分类号：O157．5 文献标识码：A 设 是一个有向图， ( )，A( )。It分别表示 本文的证明过程中将用到下述的路收缩运算。 的顶点集、弧集和顶点数。除特别声明外，文中提到 定义：设 ，Y∈V(T)，P是 上的一条( ，Y)一 的图均指无环且无平行弧的有向图。对 ，Y∈ 路，称 是收缩路P到It)得到的图。如果以下三个 (’，)，如果xy∈A(T)，则称 控制Y或 )，是 的一 条件成立： 个外弧，记作 一)，。 控制(控制 )的所有顶点组成 (1) ( 。)=( ( )、 (P))u I It)I 的集合，称为 的外邻(内邻)，记作 ( )( ( (2)Ⅳ ( )=iv；(Y)n( ( )、 (JP))， ))，并且d；( )=Ⅳ；( )，d；( )=Ⅳ；( )分别称 Ⅳ；．(tlJ)=Ⅳ；( )n ( )＼ (P) 为 的外度和内度，在上下文不引起歧义的情况下， (3)对s，t∈ ( )＼ (P)，st∈A( ) 可忽略下标 注意到，UW／)是 中的一条路，当且仅当upv是 如果对任意的 。Y∈V(T)，T中都存在( ，Y)一 中的一条路。类似可知 上存在包含It)的k-圈，当 路，则称 是强连通的。如果 ( )≥k+l，且对任 且仅当 上存在包含P的(k+I A(P)I)-圈。 意的u ( )，I u I≤k一1，都有D．U是强连通 在证明主要定理之前，我们先给出下面的引理 的，则称 是k-强连通的。 和定理。 本文中研究的图均是竞赛图，即完全图的定向 定理1… 竞赛图 是哈密尔顿图，当且仅当 图。长度为k的圈称为k．圈。一条弧被称为k-泛圈的 是强连通的。 是指，该弧包含在所有的 一圈中，此处 =k，k+l， 定理2 强连通竞赛图每个点是泛圈的。 … ， n，特别地，当k=3时，称这条弧是泛圈的，本文 定理3[ 设 是3．强连通竞赛图，则 中包 中讨论的圈都是有向圈。一个顶点被称为是外弧泛 含至少3个不同顶点 。， 。， ，，使得 。， 的所有外 圈点是指，该顶点的每一条外弧都是泛圈的。如果 弧是3．泛圈的。 的所