局部外競(jìng)賽圖上的二次外鄰

李瑞娟，孫志浩

（山西大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，山西 太原 030006）

0 引言

設(shè)D=（V，A）是一個(gè)有向圖，其中V（D）和A（D）分別表示D的頂點(diǎn)集和弧集。對(duì)于任意的頂點(diǎn)x，y∈V（D），如果（x，y）∈A（D），則稱(chēng)（x，y）是D的一條弧，y稱(chēng)為x的外鄰點(diǎn)，x稱(chēng)為y的內(nèi)鄰點(diǎn)。設(shè)H是D的任意一個(gè)頂點(diǎn)子集，也可用H表示其在D上的導(dǎo)出子圖，對(duì)D的任意的一個(gè)頂點(diǎn)x，它在H上的內(nèi)鄰點(diǎn)集和外鄰點(diǎn)集分別記為：

同樣，對(duì)任何頂點(diǎn)子集S?V（D），它在H上的內(nèi)鄰點(diǎn)集和外鄰點(diǎn)集記為：

分別為x在H上的入度和出度。x在H上的二次外鄰點(diǎn)集和二次內(nèi)鄰點(diǎn)集記為：

記d++H(x)=|N++H(x)|，d??H(x)=|N??H(x)|。以上若H=D，則可省略H。有向圖D的最小入度和最小出度分別為：

設(shè)X，Y是D的兩個(gè)不相交的頂點(diǎn)子集，從X到Y(jié)的弧集表示為：E（X，Y）=｛（x，y）∈A（D）|x∈X，y∈Y｝，記e(X，Y)=|E(X，Y)|表示X到Y(jié)的弧的數(shù)目。

在本文的討論中，考慮的所有的圈都是有向圈。有向圖D的圍長(zhǎng)g（D）是D的最小圈的長(zhǎng)度。若 g(D)≥k+1，即D沒(méi)有圈長(zhǎng)小于等于k的圈，其中k≥2，則稱(chēng)有向圖D是k-free的。本文中所考慮的有向圖都是無(wú)環(huán)且無(wú)2-圈的，一些未定義的基本符號(hào)參見(jiàn)文獻(xiàn)[1]。

1990年，Seymour提出了猜想1。

猜想 1[2]（Seymour二次鄰域猜想）任何無(wú)環(huán)無(wú)2-圈的有向圖總存在一個(gè)頂點(diǎn)v，使得d++(v)≥d+(v)。

為方便起見(jiàn)，將滿足猜想1的頂點(diǎn)稱(chēng)為圖的Seymour頂點(diǎn)。

稱(chēng)有向圖D是半完全有向圖，如果對(duì)于任意的頂點(diǎn)x，y∈V(D)，或有 (x，y)∈A(D)，或有(y，x)∈A(D)，或有 (x，y)∈A(D)且 (y，x)∈A(D)。若半完全有向圖D無(wú)2-圈，則稱(chēng)其為競(jìng)賽圖。Fisher[3]用概率方法證明了對(duì)于任何競(jìng)賽圖都存在一個(gè)Seymour頂點(diǎn)，即定理1。Havet和Thomassé[4]用中間序的方法也給出了這個(gè)定理的證明，并證明了不包含出度為0的點(diǎn)的競(jìng)賽圖中至少有兩個(gè)Seymour頂點(diǎn)。

定理1[3]每個(gè)競(jìng)賽圖中都有一個(gè)Seymour頂點(diǎn)。

2001 年，Kaneko 和 Locke[5]證明了任何最小出度小于7的有向圖都有一個(gè)Seymour頂點(diǎn)，2007 年，F(xiàn)idler和 Yuster[6]進(jìn)一步使用了中間序方法，證明了Seymour二次鄰域猜想分別在最小度為|V(D)|?2的定向圖、競(jìng)賽圖減去一個(gè)星以及競(jìng)賽圖減去一個(gè)子競(jìng)賽圖的弧集等圖的正確性。在 2008 年，Hamidoune[7]證明了任何點(diǎn)傳遞有向圖都存在一個(gè)Seymour頂點(diǎn)。2012 年，Ghazal[8]中利用加權(quán)的中間序方法證明了猜想1對(duì)于競(jìng)賽圖去掉一個(gè)廣義星得到的有向圖成立。在2013年，Lladó[9]證明了任何r出度正則且連通度至少為r?1的有向圖都存在一個(gè)Seymour頂點(diǎn)。在2021年，Bouya和Opo?rowski用線性代數(shù)的語(yǔ)言重新陳述了Seymour二次鄰域猜想，給出了若干等價(jià)命題，以期通過(guò)代數(shù)的觀點(diǎn)解決這個(gè)問(wèn)題[10]。

研究Seymour二次鄰域猜想的另一種方法是在一個(gè)有向圖D中，確定最大實(shí)數(shù) λ，使得存在一個(gè)頂點(diǎn)v滿足d++(v)≥λd+(v)。Sey?mour二次鄰域猜想要求 λ=1。2003年，Chen等[11]證明了 λ=0.657 298...是方程 2x3+x2?1=0 的唯一實(shí)根。2010年，Zhang和Zhou[12]證明了對(duì)于任何3-free有向圖D存在一個(gè)頂點(diǎn)v滿足d++(v)≥ λd+(v)，這里λ=0.675 130...是方程x3+3x2?x?1=0在區(qū)間（0，1）上的唯一實(shí)根。在 2017年，Liang 和 Xu[13]考慮了kfree有向圖(k≥3)，證明了d++(v) ≥ λkd+(v)，這里 λk是多項(xiàng)式

在區(qū)間（0，1）上的唯一實(shí)根。并且 λk隨著k的單調(diào)遞增而趨于1的，即當(dāng)k→∞時(shí)有 λk→1。當(dāng)k=3時(shí)，λk=0.682 327...。 2019年 ，Chen和Chang改進(jìn)了在3-free有向圖上的結(jié)果，給出了定理2。

定理2[14]設(shè)D是一個(gè)3-free有向圖，則存在一個(gè)頂點(diǎn)v∈V(D)，使得d++(v) ≥λd+(v)，這里λ=0.695 860… 是方程在區(qū)間（0，1）上的唯一實(shí)根。

本文將在局部外競(jìng)賽圖上研究這個(gè)猜想，從局部外競(jìng)賽圖的定義和結(jié)構(gòu)出發(fā)，確定最大實(shí)數(shù) λ，使得存在一個(gè)頂點(diǎn)v滿足d++(v)≥λd+(v)。并在某些限制條件下，如終止強(qiáng)分支無(wú)3-圈，得到了更好的下界。

1 準(zhǔn)備工作

定義1[1]若對(duì)任意的x∈V(D)，N+(x)(N?(x))的誘導(dǎo)子圖是半完全有向圖，則稱(chēng)有向圖D是局部外（內(nèi)）半完全有向圖。并且若有向圖D既是局部外半完全有向圖又是局部?jī)?nèi)半完全有向圖，則稱(chēng)D為局部半完全有向圖。

圖1 （a）一個(gè)局部外半完全有向圖；（b）一個(gè)局部半完全有向圖Fig.1 (a)A locally out-semicomplete digraph;(b)A locally semicomplete digraph

定義2[1]無(wú)2-圈的局部外（內(nèi)）半完全有向圖稱(chēng)為局部外（內(nèi)）競(jìng)賽圖。同樣，無(wú)2-圈的局部半完全有向圖稱(chēng)為局部競(jìng)賽圖。

顯然，每個(gè)競(jìng)賽圖都是局部外（內(nèi)）競(jìng)賽圖，也是局部競(jìng)賽圖。為進(jìn)一步敘述主要結(jié)論，介紹下面一些概念。

稱(chēng)有向圖是連通的，如果它的基礎(chǔ)簡(jiǎn)單圖是連通的。稱(chēng)有向圖D是強(qiáng)連通的（簡(jiǎn)稱(chēng)強(qiáng)的），如果對(duì)任意頂點(diǎn)x，y∈V(D)，都存在從x到y(tǒng)的有向路。若D不是強(qiáng)連通的，則D存在強(qiáng)連通分解：D1，D2，…，Dp，其中Di(1≤i≤p)為D的強(qiáng)連通分支（簡(jiǎn)稱(chēng)強(qiáng)分支）且

D的強(qiáng)分支可依次被標(biāo)記為D1，D2，…，Dp，并且不存在Dj到Di(i

引理1[1]每個(gè)連通的局部外（內(nèi)）半完全有向圖D有一個(gè)入（出）分枝。

定理3[1]已知D是一個(gè)局部外半完全有向圖，則

（1）設(shè)A和B是D的兩個(gè)不同的強(qiáng)分支，若有頂點(diǎn)b∈B被A中的某一個(gè)頂點(diǎn)所控制，則b被A中所有頂點(diǎn)所控制，即A?b。

（2）若D是連通的，則D的強(qiáng)分支有向圖SC（D）有一個(gè)入分枝。

定理4[1]連通有向圖D包含一個(gè)入（出）分枝當(dāng)且僅當(dāng)D僅有一個(gè)終止（初始）強(qiáng)分支。

圖2是一個(gè)非強(qiáng)連通的局部外半完全有向圖，大圓圈表示強(qiáng)分支，在兩個(gè)強(qiáng)分支之間從分支A到分支B的粗弧表示至少存在一個(gè)頂點(diǎn)b∈B，使得A?b。

圖2 一個(gè)非強(qiáng)連通的局部外半完全有向圖的強(qiáng)連通分解Fig.2 Strong decomposition of a non-strong locally out-semicomplete digraph

本文的一些相關(guān)證明依賴(lài)局部外（內(nèi)）競(jìng)賽圖的結(jié)構(gòu)特征，上述關(guān)于局部外（內(nèi)）半完全有向圖的定義和定理顯然對(duì)于局部外（內(nèi)）競(jìng)賽圖也適用。

2 局部外競(jìng)賽圖上頂點(diǎn)的二次外鄰

定理5對(duì)于任意的局部外競(jìng)賽圖D，總存在一個(gè)頂點(diǎn)v∈V(D)，使得d++(v)≥ λd+(v)，這 里 λ=0.689 897…是 方程 5x2?2x?1=0的唯一正實(shí)根。

證明對(duì)于只有1個(gè)或2個(gè)頂點(diǎn)的有向圖，定理5顯然是成立的。設(shè)D是一個(gè)有n≥3個(gè)頂點(diǎn)的局部外競(jìng)賽圖，用反證法，假設(shè)D中不存在滿足d++(v)≥λd+(v)的頂點(diǎn)，即對(duì)任意的 頂 點(diǎn)v∈V(D)，有d++(v)< λd+(v)，這 里λ=0.689 897…是方程 5x2?2x?1=0的唯一正實(shí)根。

由于每個(gè)局部競(jìng)賽圖都是局部外競(jìng)賽圖，則有下面的推論成立。

推論1對(duì)于任意的局部競(jìng)賽圖D，總存在一個(gè)頂點(diǎn)v∈V(D)，使得d++(v)≥λd+(v)，這里 λ=0.689 897…是方程 5x2?2x?1=0的唯一正實(shí)根。

Caccetta-H?ggkvist猜想敘述為最小出度不小于r的n階有向圖含有長(zhǎng)度不大于的有向圖。下面的命題描述了Caccetta-H?ggkvist猜想與Seymour二次鄰域猜想的關(guān)系。

命題1[11]對(duì)于一個(gè)含有n個(gè)頂點(diǎn)的無(wú)環(huán)且無(wú)2-圈的有向圖D，若存在一個(gè)頂點(diǎn)v∈V(D)，使得d++(v)≥λd+(v)，這里λ是一個(gè)正實(shí)數(shù)。如果 min{δ?(D)，δ+(D)}≥n/(2+λ)，則有向圖D有3-圈。

由命題1可以看出，當(dāng)最小入度和最小出度都至少是n/3時(shí)，即λ=1時(shí)，Seymour二次鄰域猜想蘊(yùn)含了Caccetta-H?ggkvist猜想中含有長(zhǎng)度為3的有向圈的情況。對(duì)于局部外競(jìng)賽圖，可得出以下推論。

推論2設(shè)D是一個(gè)含有n個(gè)頂點(diǎn)的局部外競(jìng)賽圖，如果 min{δ?(D)，δ+(D)}≥0.3717n，則D包含3-圈。

證明由定理5知，存在一個(gè)頂點(diǎn)v∈V(D)，使d++(v)≥λd+(v)，這里λ=0.689 897…是方程 5x2?2x?1=0的唯一正實(shí)根。又由命題1知，若min{δ?(D)，δ+(D)}≥0.3717n，也就有min{δ?(D)，δ+(D)} ≥n/(2+λ)，所以D包 含3-圈。

3 局部外競(jìng)賽圖的終止強(qiáng)分支上的二次外鄰

下面考慮局部外競(jìng)賽圖的終止強(qiáng)分支上的二次外鄰。由引理1知，局部外競(jìng)賽圖有一個(gè)入分枝。又根據(jù)定理4可得，局部外競(jìng)賽圖僅有一個(gè)終止強(qiáng)分支。

引理2對(duì)任意非強(qiáng)連通的有向圖D，它的終止強(qiáng)分支上的Seymour頂點(diǎn)也是整個(gè)有向圖上的Seymour頂點(diǎn)。

證明對(duì)任意非強(qiáng)連通的有向圖D都存在強(qiáng)分支無(wú)圈序，所以至少存在一個(gè)終止強(qiáng)分支，記D的一個(gè)終止強(qiáng)分支為Dt。若Dt中存在一個(gè)Seymour頂點(diǎn)v，使得由于不存在從Dt中發(fā)出的到其他強(qiáng)分支的弧，有且，從而，所以v也是D的Seymour頂點(diǎn)。

引理3局部外競(jìng)賽圖的初始強(qiáng)分支和終止強(qiáng)分支也是局部外競(jìng)賽圖，且局部外競(jìng)賽圖的終止強(qiáng)分支上的Seymour頂點(diǎn)也是整個(gè)局部外競(jìng)賽圖上的Seymour頂點(diǎn)。

證明設(shè)D是一個(gè)局部外競(jìng)賽圖，顯然D的任意頂點(diǎn)子集誘導(dǎo)的子有向圖是局部外競(jìng)賽圖，因此，D的初始強(qiáng)分支和終止強(qiáng)分支仍然是局部外競(jìng)賽圖。再由引理2可知，局部外競(jìng)賽圖的終止強(qiáng)分支上的Seymour頂點(diǎn)也是整個(gè)局部外競(jìng)賽圖上的Seymour頂點(diǎn)。

推論3若局部外競(jìng)賽圖D的終止強(qiáng)分支只包含一個(gè)頂點(diǎn)v，則頂點(diǎn)v是D的一個(gè)Seymour頂點(diǎn)。

定理6如果局部外競(jìng)賽圖D的終止強(qiáng)分支Dt不包含3-圈，則存在一個(gè)頂點(diǎn)v∈V(D)，使得d++(v)≥ λd+(v)，這里λ=0.695 860…是方程在區(qū)間（0，1）上的唯一實(shí)根。

證明設(shè)局部外競(jìng)賽圖D的終止強(qiáng)分支為Dt。若Dt不包含3-圈，即Dt是3-free有向圖，由定理2知，存在一個(gè)頂點(diǎn)v∈V(Dt)，使得，又根據(jù)引理2的證明可知，有，從而存在一個(gè)頂點(diǎn)v∈V(Dt)?V(D)，使得d++(v) ≥ λd+(v)，這里 λ=0.695 860…是方程在區(qū)間（0，1）上的唯一實(shí)根。

注記由于局部?jī)?nèi)競(jìng)賽圖可以看成是某個(gè)局部外競(jìng)賽圖的逆圖，以及定理6的證明，易知下面的結(jié)論成立：

（1）對(duì)于任意的局部?jī)?nèi)競(jìng)賽圖D，總存在一個(gè)頂點(diǎn)v∈V(D)，使得d??(v)≥λd?(v)，這里λ=0.689 897…是方程 5x2?2x?1=0的唯一正實(shí)根。

（2）如果局部?jī)?nèi)競(jìng)賽圖D的一個(gè)終止強(qiáng)分支Dt不包含 3-圈，則存在一個(gè)頂點(diǎn)v∈V(D)，使得d++(v) ≥ λd+(v)，這里λ=0.695 860…是方程在區(qū)間（0，1）上的唯一實(shí)根。