類競賽圖.pdf

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

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

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

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

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

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

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

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

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