類競賽圖.pdf

1、一個(gè)有向圖是半完全的，如果它的任意兩個(gè)不同的頂點(diǎn)之間至少有一條弧.沒有2圈的半完全有向圖是競賽圖.競賽圖無疑是有向圖中一類非常重要的圖，它已經(jīng)被廣泛研究.1990年Bang-Jensen首次引進(jìn)了競賽圖的一類推廣圖-局部半完全有向圖.對(duì)有向圖D中任一頂點(diǎn)x，如果它的內(nèi)鄰集和外鄰集誘導(dǎo)的子圖都是半完全有向圖，則稱D是局部半完全有向圖.1993年Bang-Jensen引進(jìn)了弧局部半完全有向圖.對(duì)有向圖D中任意兩個(gè)相鄰的頂點(diǎn)x，y，如果x的內(nèi)

2、鄰和y的內(nèi)鄰是相鄰的或者是同一個(gè)頂點(diǎn)，且x的外鄰和y的外鄰是相鄰的或者是同一個(gè)頂點(diǎn)，則稱有向圖D是弧局部半完全有向圖.1995年Bang-Jensen和Huang引進(jìn)了準(zhǔn)傳遞有向圖.2004年Bang-Jensen引進(jìn)了3準(zhǔn)傳遞有向圖.2011年，Hernández-Cruz引進(jìn)了k準(zhǔn)傳遞有向圖.對(duì)有向圖D中任意一條長為k的路，若起點(diǎn)和終點(diǎn)是相鄰的，則稱有向圖D是k準(zhǔn)傳遞有向圖.當(dāng)k=2時(shí)，k準(zhǔn)傳遞有向圖也稱為準(zhǔn)傳遞有向圖.這幾類有向圖

3、顯然都是競賽圖的推廣圖，即這些有向圖中包含競賽圖作為子圖.有關(guān)這些圖類的研究已逐漸發(fā)展成為一個(gè)較成熟的研究領(lǐng)域.在本文中，我們稱競賽圖的推廣圖為類競賽圖，并就類競賽圖中的若干問題進(jìn)行了研究.
　　本文共分四章.第一章介紹了無向圖和有向圖中的一些基本概念以及論文內(nèi)容的安排.
　　第二章研究了競賽圖和局部半完全有向圖中的王.2.1節(jié)介紹了類競賽圖中關(guān)于王的一些研究成果.2.2節(jié)研究了強(qiáng)連通的競賽圖中的k王（k≥3），并且證明了強(qiáng)

4、連通的競賽圖中至少有k+1個(gè)k王，并給出正好有k+1個(gè)k王時(shí)競賽圖的結(jié)構(gòu).已經(jīng)知道每一個(gè)競賽圖中至少有一個(gè)2王.每一個(gè)沒有內(nèi)度為零的頂點(diǎn)的競賽圖中至少有3個(gè)2王.2.2節(jié)還給出了正好有3個(gè)2王的競賽圖的結(jié)構(gòu).
　　在2.3節(jié)，我們研究了局部半完全有向圖中的k王，并且證明了，對(duì)局部半完全有向圖D，下面幾條成立:
　　(a)假設(shè)D不是強(qiáng)連通的且D'1，D'2，…，D'r是D的半完全分解.若r=2，則D包含一個(gè)2王;若r≥3，則D

5、包含一個(gè)r-1王;
　　(b)假設(shè)D是一個(gè)強(qiáng)連通的、圓可分解的局部半完全有向圖，圓分解為D=R[S1，S2，…，Sp].則D包含一個(gè)g(R)王，其中g(shù)(R)是R的圍長;
　　(c)假設(shè)D是一個(gè)強(qiáng)連通的、非圓可分解的局部半完全有向圖.則D包含一個(gè)2王.
　　第三章研究了弧局部內(nèi)半完全有向圖.在2004年，Bang-Jensen刻畫了強(qiáng)連通的弧局部半完全有向圖的結(jié)構(gòu)，并證明了弧局部半完全有向圖D中有哈密頓圈當(dāng)且僅當(dāng)D是強(qiáng)連

6、通的且有圈因子.有向圖H1，H2，H3，H4的定義在第一章可以找到.Bang-Jensen定義不包含H1和H2作為子圖的有向圖為弧局部半完全有向圖.在本文中，我們定義不包含H1作為子圖的有向圖為弧局部內(nèi)半完全有向圖;不包含H2作為子圖的有向圖為弧局部外半完全有向圖;不包含H3作為子圖的有向圖為弧準(zhǔn)傳遞有向圖;不包含H4作為子圖的有向圖為3反路-準(zhǔn)傳遞有向圖.Galeana-Sánchez定義不包含H3作為子圖的有向圖為3準(zhǔn)傳遞有向圖.本

7、文使用了3準(zhǔn)傳遞有向圖這個(gè)概念.
　　Bang-Jensen猜想:一個(gè)弧局部內(nèi)半完全有向圖D中有哈密頓圈當(dāng)且僅當(dāng)D是強(qiáng)連通的且有圈因子.在3.1節(jié)，我們介紹了弧局部半完全有向圖的一些研究結(jié)果.在3.2節(jié)，我們刻畫了強(qiáng)連通的弧局部內(nèi)半完全有向圖的結(jié)構(gòu)并由此證明了Bang-Jensen的猜想是正確的.
　　Laborde，Payan和Xuong提出了下面的猜想:每一個(gè)有向圖中都存在一個(gè)獨(dú)立集與每一條最長的路是相交的.在3.3節(jié)，

8、我們給出了不強(qiáng)連通的弧局部內(nèi)半完全有向圖的性質(zhì)，并由此證明對(duì)弧局部內(nèi)半完全有向圖這個(gè)猜想是正確的.
　　第四章研究了k準(zhǔn)傳遞有向圖.在4.1節(jié)，我們介紹了k（準(zhǔn)）傳遞有向圖的一些研究成果.若有向圖D中任意一條長為k路，（起點(diǎn)和終點(diǎn)是相鄰的）起點(diǎn)控制終點(diǎn)，則稱有向圖D是k（準(zhǔn)）傳遞有向圖.在4.2節(jié)，給出了不強(qiáng)連通的3準(zhǔn)傳遞有向圖的性質(zhì).在4.3節(jié)，使用4.2節(jié)的結(jié)果證明了對(duì)3準(zhǔn)傳遞有向圖上一章Laborde，Payan和Xuong

9、提出的猜想是正確的.
　　Hernández-Cruz猜想:無向圖G可定向?yàn)?準(zhǔn)傳遞有向圖當(dāng)且僅當(dāng)它可以定向?yàn)?傳遞有向圖.在4.4節(jié)，我們證明這個(gè)猜想是正確的.
　　在4.5節(jié)，我們研究了3準(zhǔn)傳遞有向圖中的k王，并且證明3準(zhǔn)傳遞有向圖中存在4王.
　　Hernández-Cruz猜想:設(shè)k-1是一個(gè)質(zhì)數(shù)，D是一個(gè)階至少為k+1的強(qiáng)連通k傳遞有向圖.若D中包含一條長為n的有向圈，并且D不是對(duì)稱的k+1圈，其中n≥k，(