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

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


本文編號(hào)：3714853