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

第37卷 第5期 应 用 数 学 学 报 Vo1．37No．5 2014年 9月 ACTAMATItEMATICAEAPPLICATAESINICA Sep．，2014 k一强连通竞赛图外弧4泛圈点的研究 李艳艳 (西安工业大学理学院，西安710021) (E—mail：1yy8261286@163．corn) 摘 要 2006年，Feng等人证明了每个 一强连通竞赛图至少包含k+1个外弧4泛圈点．2010 年，郭巧萍等人证明了每个 一强连通竞赛图至少包含 k+2个外弧 5泛圈点．在这篇文章中， 我们将对 一强连通竞赛图的外弧 4泛圈点做进一步的研究． 关键词 竞赛图；强连通；外弧泛圈点 MR(2000)主题分类 62G05；62N01 中图分类 O212．7 1 引言 对于文中其它未定义的图论术语和记号参见 1『1_ 设 D是一个有向图，V(D)， (D)，n分别表示J[)的顶点集，弧集和顶点数．除特别 声明外，本文中提到的图均指无环且无平行弧的有向图．对X，Y∈ (D)，如果xy∈A(D)， 那么称 控制 Y，xy是 的一：条外弧，记为 — Y． 控制 (控制 z)的顶点组成的集 合，称为 的外邻 (内邻)，记作崂 ()( ())．我们用d去()=f崂 ()I表示 的外 度，并且用 dD(X)=IⅣ ()I表示 的内度．竞赛图是指完全图的定向图．如果对任意 的 ，Y∈V(D)都存在 (，)一路，则称 D是强连通的．如果 f()f +1，且对任意 U (D)，IU1 一1，都有 D～ 是强连通的，那么称 ．D是 一强连通的．如果D是 k一强连通的，但不是 (+1)一强连通的，那么定义 D的强连通度为 ．显然，若J[)是 一 强连通的，则D是 (k一1)一强连通的．如果一条弧或一个顶点包含在所有 i(kSi 礼) 圈中，那么它被称为 泛圈的．特别地，当 =3时，称为泛圈的．外弧泛圈点是指这 个点的所有外弧都是泛圈的． 在有向图D中，一般我们用△+：max{d5()： ∈ (D))与△一=max{d3()： X∈ (D))表示 D的最大外度和最大内度，用 +：min{d+(x)： ∈ (D))与 一= min{d3(X)：X∈ (D))表示 D的最小外度和最小内度．如果有向图D有一个有向圈 本文 2012年 11月 8日收到．2013年 1月 6日收到修改稿 892 应 用 数 学 学 报 37卷 (路) 满足 ()= (D)，那么称这个圈 (路)为Hamilton圈 (路)．若有向图D含有一 个 Hamilton圈，则称 D为 Hamilton有向图．设 S (D)，我们用ms)表示D 中由 顶点集 s诱导生成的子图． 定义 设X，Y∈ (D)，P是 D上的一条 (z，)．路，称J[)是收缩P到W得到的图． 如果下面三条成立： 1．V(D)=((D)＼(P))u{)． 2．畦 ，(W)：N+()n((D)＼(P))； ，(W)=N一()n((J[))＼(P))． 3．对8，t∈ (J[))＼(P)，st∈A(D)当且仅当st∈ (J[))． 注意到，UWV是D 中的一条路，当且仅当uPv是 D中的一条路．类似地，D 中 存在包含tU的 一圈，当且仅当D中存在包含 P的 (庇+lA(P)f)一圈． 2 主要结论 引理 1[。】每个竞赛图都包含一条Hamilton路． 引理 2。【】竞赛图 是Hamilton图，当且仅当 是强连通的． 引理 3[]设 是一个 3一强连通竞赛图，Ul，X∈V(T)满足 d+(，“1)= ()且 X∈Ⅳ+(1)．如果存在 Y∈Ⅳ+(1)使得 Y— ，那么 的所有外弧在 中都是 4泛圈 的． 引理 4【]设 是一个2一强连通竞赛图，如果xy∈A()，满足d+(Y) d+()，那么 是泛圈的． 引理5[]设J[)是强连通有向图，z∈ (D)．如果D-x是竞赛图，且d去