關(guān)于一類圖的可圈性與強(qiáng)連通可推性.pdf

1、設(shè)G是無(wú)向簡(jiǎn)單圖，定義Gk為G的k次冪，其頂點(diǎn)集V(Gk)=V(G)，邊集E(Gk)={uv|dG(u，v)≤k，u，v∈V(G)}。設(shè)D是一有向圖，如果D中存在有向圈C含D中所有頂點(diǎn)，則稱C為D的哈密爾頓有向圈。如果D中含有一個(gè)哈密爾頓有向圈，則稱D為哈密爾頓有向圖。若對(duì)有向圖D中任意兩個(gè)不同頂點(diǎn)x，y，D中既存在從x到y(tǒng)的有向路，又存在從y到x的有向路，則稱D為強(qiáng)連通有向圖.在有向圖D中，定義推點(diǎn)v為將D中所有與v關(guān)聯(lián)的弧反向.若一

2、同構(gòu)于H的有向圖可通過(guò)對(duì)有向圖D施行一系列推點(diǎn)運(yùn)算得到，則稱D可推為H.若某簡(jiǎn)單圖的所有定向均可推成哈密爾頓有向圖，則稱其為可圈圖。 Camion的一個(gè)著名定理宣稱一個(gè)競(jìng)賽圖是強(qiáng)連通有向圖當(dāng)且僅當(dāng)其為哈密爾頓有向圖。Klostermeyer證明了圈平方的任意一個(gè)定向可推成強(qiáng)連通有向圖當(dāng)且僅當(dāng)其可推成哈密爾頓有向圖。在本文中，我們將證明路的三次方的任意一個(gè)定向可推成強(qiáng)連通有向圖當(dāng)且僅當(dāng)其可推成哈密爾頓有向圖。作為推論，當(dāng)n≥4和n