有向圖D是準傳遞的,如果對D中任意三個不同的頂點x, y和z,只要在D中存在弧xy, yz, x和z之間就至少存在一條弧. Seymour二次鄰域猜想為:在任何一個定向圖D中都存在一個頂點x,滿足d_D⁺（x）d_D⁺⁺（x）.這里,定向圖是指沒有2圈的有向圖.稱滿足Seymour二次鄰域猜想的點為Seymour點. Fisher證明了Seymour二次鄰域猜想適用于競賽圖,也就是每個競賽圖至少包含一個Seymour點. Havet和Thomassé證明了,無出度為零的點的競賽圖至少包含兩個Seymour點.注意到,競賽圖是準傳遞有向圖的子圖類.研究Seymour二次鄰域猜想在準傳遞定向圖上的正確性,通過研究準傳遞定向圖與擴張競賽圖的Seymour點之間的關系,證明了準傳遞定向圖上Seymour二次鄰域猜想的正確性,得到:每個準傳遞定向圖至少包含一個Seymour點;無出度為零的點的準傳遞定向圖至少包含兩個Seymour點. 

【文章頁數(shù)】：8 頁


本文編號：3714853